Python Course #6: Multiplying and Dividing Binary Numbers
Post
Cancel

# Python Course #6: Multiplying and Dividing Binary Numbers Now that you can add and subtract binary numbers (Python Course #5: Adding and Subtracting Binary Numbers),let’s take it one step further and multiply and divide binary numbers.

# Multiplying Binary Numbers

First, look at decimal multiplication and how you probably learned how to do it in school. Take, for example, the multiplication of $$23\cdot 45$$. In the first step, you multiply $$3$$ with $$4$$ (the last digit of the first number/factor and the first digit of the second number), which is 12. The 2 is written directly under the first digit of the second number while the 1, representing the 10 in 12, is carried over to the next position:

$\begin{eqnarray} 2\underline{3} \cdot \underline{4}5\\\hline \quad_1 2\hspace{0.5em} \end{eqnarray}$

In the next step, the next digit of the first number is multiplied by the first digit of the second number ($$2\cdot 4$$). The result of this calculation represents the next decimal position. It is therefore written down in front of the result of the first multiplication, and if a digit was carried over from the previous result, they are added together:

$\begin{eqnarray} \underline{2}3 \cdot \underline{4}5\\\hline 92\hspace{0.5em} \end{eqnarray}$

This step is repeated until all digits of the first number have been multiplied by the first digit of the second number. Then, the second digit of the second number is used and multiplied with every digit of the first number going from right to left. So in this example, the first digit pair that has to be multiplied is: $$3\cdot 5$$. This multiplication is now written under the number coming from the multiplication of the first digit of the second number with all the digits of the first number. However, it is shifted one digit back:

$\begin{eqnarray} 2\underline{3} \cdot 4\underline{5}\\\hline 92\hspace{0.5em}\\ \quad_1 5 \end{eqnarray}$

And as you probably already guessed now the next pair of digits to multiply is $$2\cdot 5$$:

$\begin{eqnarray} 2\underline{3} \cdot 4\underline{5}\\\hline 92\hspace{0.5em}\\ 115 \end{eqnarray}$

And if you have more digits in the second number, this step is repeated until every digit of the first number is multiplied with every digit of the second number.

The last step is to add all the results together which will give you the result of the whole multiplication:

$\begin{eqnarray} 23 \cdot 45\\\hline 92\hspace{0.5em}\\ +\hspace{0.5em}115\\\hline 1035 \end{eqnarray}$

The binary multiplication works in the exact same way. But instead of decimal numbers, binary numbers are used. And as only the multiplications including the numbers $$1$$ and $$0$$ have to be taken into account, it becomes much easier. Because every multiplication including a $$0$$ results in $$0$$ and only $$1\cdot 1$$ is $$1$$. And this means there are no carry-bits when multiplying the bit with each other, which is why it is so much easier to multiply binary numbers.

As an example lets multiply $$10_{10} = 1010_2$$ with $$5_{10} = 10_2$$. In the first step the last bit of the first number is multiplied with the first bit of the second number:

$\begin{eqnarray} 101\underline{0} \cdot \underline{1}01\\\hline 0\hspace{0.5em}\hspace{0.5em} \end{eqnarray}$

Since there are no carry-bits when multiplying only single ones and zeros, you can carry one multiplying the other bits of the first number with the first digit of the second number.

$\begin{eqnarray} \underline{1010} \cdot \underline{1}01\\\hline 1010\hspace{0.5em}\hspace{0.5em} \end{eqnarray}$

Now take a look at the first row. It is the same number as the first number of the whole multiplication. Now you can go to the next digit of the second number and multiply it with all digits of the first one.

$\begin{eqnarray} \underline{1010} \cdot 1\underline{0}1\\\hline 1010\hspace{0.5em}\hspace{0.5em}\\ 0000\hspace{0.5em} \end{eqnarray}$

You can see that the whole row is $$0$$ because $$0$$ multiplied with anything is always $$0$$. This is the second reason why it is so easy to multiply binary numbers compared to decimal numbers. Now you can do the multiplications with the last bit of the second number. Which is just writing down the first number starting from under the last bit:

$\begin{eqnarray} \underline{1010} \cdot 1\underline{0}1\\\hline 1010\hspace{0.5em}\hspace{0.5em}\\ 0000\hspace{0.5em}\\ 1010 \end{eqnarray}$

To make it even easier you can skip $$0$$ zero bits of the second number entirly and shift the beginning of the next row to the right by one more bit. Which would result in:

$\begin{eqnarray} \underline{1010} \cdot 1\underline{0}1\\\hline 1010\hspace{0.5em}\hspace{0.5em}\\ 1010 \end{eqnarray}$

The last step is, as in the decimal multiplication, adding up all rows. And if you forgot how to add binary numbers just have a quick look at Python Course #5: Adding and Subtracting Binary Numbers:

$\begin{eqnarray} \underline{1010} \cdot 1\underline{0}1\\\hline 1010\hspace{0.5em}\hspace{0.5em}\\ \oplus\quad\quad1010\\\hline 110010 \end{eqnarray}$

When you got more than two rows to add together it sometimes makes sense to split up the addition into smaller chunks and add them together one after another.

When multiplying a binary number with a power of $$2$$, such as $$2$$, $$4$$, $$8$$, $$16$$, etc., you can speed up your calculation even more. Because for every multiplication with a $$2^x \geq 2$$ you can add a zero at the end of the number multiplied with a power of $$2$$. This operation is called left shift because every bit is shifted to the left-hand side. Take, for example,

$42_{10} = 101010_2$

and you want to multiply it by $$4$$. When you append one $$0$$ you get

$1010100_2 = 84_{10}$

and when you add another $$0$$ you get

$10101000_2 = 168_{10}$

This trick is used quite often in computer science and engineering because multiplication itself can be very costly in terms of time. After all, it consists of many tiny single-bit multiplications and several additions. The left-shift operation is also available in Python as <<. You can try out this code to check it:

1 2 3 4 x = 42 print(f"{x} = {x:b}") y = x << 2 print(f"{y} = {y:b}") 

# Dividing Binary Numbers

Now that you know how to multiply binary numbers let’s look at the most complicated operation, the division. Obviously, you only got integer numbers in binary; this means most divisions will have a remainder. As binary multiplication uses single-bit multiplications and additions, the counter operation division uses primary divisions and subtractions to divide two binary numbers.

In this example $$132_{10} = 10000100_2$$ is going to be divided by $$13_{10} = 1101_2$$. As a first step you need the twos’ complement negative of $$13_{10} = 1101_2$$ which is $$10011_2$$ (expanded by one bit such that the MSB is set to $$1$$). To start with the division process write down both numbers and expand the dividend with a $$0$$ in the front to mark it as a positive number, leave some space below the numbers, and add an equal sign at the end:

$010000100 \div 1101 =$

Take the first $$n$$ bits (the length of the divisor) starting from the first $$1$$ of the dividend and compare it to the divisor than there are only three possibilities the divisor is smaller, equal, or larger than the selected bits of the dividend. In this example the bits to check in the dividend are $$1000$$; here you can see that those bits are less than the dividend. Since the divisor does not “fit” into those bits (one could also say the divisor is contained $$0$$ times in those bits), you need a more significant number to “fit” the divisor. To track that the divisor is contained $$0$$ times in the selected bits, write a $$0$$ after the equal sign and note four $$0000$$ under the bits the divisor does not “fit” into.

$\begin{eqnarray} 0\underline{1000}0100 \div 1101 = 0\\ 0000\quad\quad\quad\quad\quad\quad\quad\hspace{0.2em} \end{eqnarray}$

Now you can subtract $$0000$$ from $$1000$$ which is just $$1000$$ and write it under $$0000$$ such that the bits align:

$\begin{eqnarray} 010000100 \div 1101 = 0\\ \underline{0000}\quad\quad\quad\quad\quad\quad\quad\\ 1000\quad\quad\quad\quad\quad\quad\quad\hspace{0.1em}\\ \end{eqnarray}$

Now you can expand this number to “fit” $$1101$$ by getting the next bit from the dividend:

$\begin{eqnarray} 01000\underline{0}100 \div 1101 = 0\\ \underline{0000}\quad\quad\quad\quad\quad\quad\quad\hspace{0.1em}\\ 10000\hspace{0.6em}\quad\quad\quad\quad\quad\quad\hspace{0.1em}\\ \end{eqnarray}$

Now $$1101$$ fits into $$10000$$. And one neat property of using this technique is that the divisor either fits $$0$$ or $$1$$ times into the bits coming from the dividend. And this time, the divisor can be subtracted from the string of bits “pulled down” from the dividend. The twos’ complement of the divisor is used to perform the subtraction. The fact that the divisor fits into them is tracked by writing a $$1$$ at the end of the number coming after the equal sign.

$\begin{eqnarray} 010000100 \div 1101 = 01\\ \underline{0000}\quad\quad\quad\quad\quad\quad\quad\hspace{0.4em}\\ 10000\hspace{0.6em}\quad\quad\quad\quad\quad\quad\hspace{0.4em}\\ \underline{\oplus\hspace{0.3em}10011}\hspace{0.5em}\quad\quad\quad\quad\quad\quad\hspace{0.4em}\\ \cancel{1}00011\hspace{0.6em}\quad\quad\quad\quad\quad\quad\hspace{0.4em}\\ \end{eqnarray}$

After the subtraction, the next bit from the divisor can be pulled down. Afterward, you have to check if $$1101$$ fits into $$111$$ which it doesn’t. So go ahead and subtract $$0000$$ from it and track the fact that $$1101$$ is contained in $$111$$ $$0$$ times by writing another $$0$$ at the end of the numbers coming after the equal sign.

$\begin{eqnarray} 010000\underline{1}00 \div 1101 = 010\\ \underline{0000}\quad\quad\quad\quad\quad\quad\quad\hspace{1em}\\ 10000\hspace{0.6em}\quad\quad\quad\quad\quad\quad\hspace{1em}\\ \underline{\oplus\hspace{0.3em}10011}\hspace{0.5em}\quad\quad\quad\quad\quad\quad\hspace{1em}\\ 000111\hspace{0.1em}\quad\quad\quad\quad\quad\quad\hspace{1em}\\ \underline{0000}\hspace{0.1em}\quad\quad\quad\quad\quad\quad\hspace{1em}\\ 0111\hspace{0.1em}\quad\quad\quad\quad\quad\quad\hspace{1em} \end{eqnarray}$

Now you can get the next bit from the divisor. This time you have to check if $$1101$$ is contained in $$1110$$ and that is actually the case so you can subtract $$1101$$ from $$1110$$ by adding its twos’ complement and adding a $$1$$ to the end of the result.

$\begin{eqnarray} 0100001\underline{0}0 \div 1101 = 0101\\ \underline{0000}\quad\quad\quad\quad\quad\quad\quad\hspace{1.4em}\\ 10000\hspace{0.6em}\quad\quad\quad\quad\quad\quad\hspace{1.4em}\\ \underline{\oplus\hspace{0.3em}10011}\hspace{0.5em}\quad\quad\quad\quad\quad\quad\hspace{1.4em}\\ 000111\hspace{0.1em}\quad\quad\quad\quad\quad\quad\hspace{1.4em}\\ \underline{0000}\hspace{0.1em}\quad\quad\quad\quad\quad\quad\hspace{1.4em}\\ 01110\hspace{0.7em}\quad\quad\quad\quad\quad\hspace{1.4em}\\ \underline{\oplus\hspace{0.3em}10011}\hspace{0.6em}\quad\quad\quad\quad\quad\hspace{1.4em}\\ 00001\hspace{0.7em}\quad\quad\quad\quad\quad\hspace{1.4em} \end{eqnarray}$

After this step, only one bit is left from the divisor. Adding this bit results in $$10$$ into which $$1101$$ does not fit, which again means subtracting $0000$ and adding a $0$ to the result. After the subtraction, you are left with the remaining $$10$$, which is the remainder of the division.

$\begin{eqnarray} 01000010\underline{0} \div 1101 = 01010\hspace{0.4em}R: 10\\ \underline{0000}\quad\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ 10000\hspace{0.6em}\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ \underline{\oplus\hspace{0.3em}10011}\hspace{0.5em}\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ 000111\hspace{0.1em}\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ \underline{0000}\hspace{0.1em}\quad\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ 01110\hspace{0.7em}\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ \underline{\oplus\hspace{0.3em}10011}\hspace{0.6em}\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ 000010\hspace{0.2em}\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{1em}\\ \underline{0000}\hspace{0.2em}\quad\quad\quad\quad\quad \quad\quad\quad\quad\hspace{0.9em}\\ 10\hspace{0.2em}\quad\quad\quad\quad\quad\quad\quad\quad\quad\hspace{0.9em} \end{eqnarray}$

Checking the result in decimal shows that $$132\div 13 = 10\hspace{0.4em}R:2$$ with $$10_{10} = 1010_2$$ and $$2_{10} = 10_2$$. To sum up, here are the steps of the binary division:

1. Check if the divisor fits into the left-most bits of the dividend that aren’t used yet.
• if the divisor doesn’t fit into it, subtract a 0 and add a $$0$$ to the result.
• if the divisor does fit into it, subtract (add the twos’ complement) and adds a $$1$$ to the result.
2. Check if there are still bits available in the dividend.
• if there are bits available, pull down the next bit and go the step 1.
• if there aren’t any bits available, the last subtraction result is the remainder, and the number after the equal sign is the result.

You can also get the result with the remainder in Python using the integer division operator // and the modulo operator %:

1 2 3 4 5 6 7 x = 132 y = 13 d = x // y r = x % y print(d,"R:", r) 

And as a last operation there is the left-shift >> that is the inverse operation of the right-shift << and will divide by 2 for every bit that the number is shifted:

1 2 3 4 x = 10 print(f"{x} = {x:b}") y = x >> 2 print(f"{y} = {y:b}") 

And this concludes this article on how to multiply and divide binary numbers. I encourage you to try out binary multiplication and division yourself because doing things yourself is one of the best ways to learn.