Division is probably the hardest of the four basic arithmetic operations. In this post we walk through an easy to follow, step-by-step process that you can use to divide any two binary numbers.The process we will walk through today requires solving a number of smaller problems on the way to producing our final answer. Before we dive in though, we first need to establish a common understanding, a definition of some terminology, that I will use later in the post to explain some of the steps.
As you will no doubt remember from your time at school, a division problem involves two numbers and is usually written as follows:
Beneath the line we have the numerator or dividend. This is the number we want to divide. Above the line we have the denominator or divisor. This is the number we are going to divide into the dividend. The result of the division operation is called the quotient.
Four Steps to Division
At it’s most basic, long division is a four-step process that is repeated for each of the digits in the dividend. The steps in the process build on the knowledge we have learnt from my previous posts on multiplication and subtraction and as such has the following steps:
Division: Starting with the first digit of the dividend, we attempt to divide it by the divisor. This results in a quotient (which may be zero).
Multiplication: Once we have worked out the quotient we use it to multiply the divisor to obtain a product.
Subtraction: Having calculated the product in the previous step, we subtract that from the working dividend to calculate a remainder.
Bring Down the Next Digit: The final step, is then to bring down the next digit in our original dividend, combine it with the remainder in the previous step and form a new working dividend. At this point, the process is repeated.
Let’s look some examples of applying this process, first in decimal (just so you get the hang of it), and then we’ll move on to looking at how we do the same thing in binary.
Let’s imagine that we were trying to divide the decimal number 160.65 by the decimal number 21. Using the process I have outlined above, here are the steps involved:
First, we write out our division problem. We check to see whether our divisor has a radix point. In this example it hasn’t but if it did, we would keep moving the radix point one place to the right in both the divisor and dividend until the radix point had been eliminated from the divisor. This will allow us to write our division problem in terms of a divisor that is a whole-number.
Sub Problem 1
In step 1 of the process we perform division. We start by taking the first digit or our dividend (the 1 of 160.65) as our current working dividend and then look at whether our divisor (21) will fit into it. The answer in this case is no because 21 is greater than 1. We therefore put a 0 in the first column of our result (we write the result above the line as you can see from the illustration).
Following that we perform step 2 where we multiply our quotient by our divisor. In this case is 21 x 0 = 0 so we write 0 as the product.
In step 3, we subtract the product from our current working dividend to obtain a remainder. 1 – 0 = 1 so we put 1 as our remainder.
In the final step, we bring down the next digit of our original dividend (the first 6 of 160.65) to form a new working dividend of 16 and restart the process.
Sub Problem 2
Back at Step 1, we again look at whether our divisor can be divided into our working dividend. As 21 is greater than 16 the answer is no and we put a zero as the next number in our result.
Having calculated our quotient, we multiply it by our divisor to obtain a new product. 21 x 0 = 0 so we write 0 as the product.
The next step is to subtract our product from our current working dividend. 16 – 0 = 16 so we write 16 as the remainder.
The final step in this sub-problem is to bring down the next digit or our original quotient (in this case the 0 of the 160.65) to form a new working dividend of 160.
Sub Problem 3
Back at step 1 again, we attempt to divide our current working dividend by the divisor. This time we get an answer other than zero and with a bit of a guess calculate that 21 can fit into 160 around 7 times. We therefore put 7 as our the next digit in our result.
In step 2, we take the quotient we just calculated and multiply it by our divisor. In this case, 7 x 21 = 147 so we write that as the product.
The next step is to subtract the product from the current working dividend. 160 – 147 = 13 so we write 13 as our remainder.
The last step is to bring down the next number (the second 6 of 160.65) to create a new working dividend of 136.
Sub Problem 4
You should be getting the idea by now. We divide the current working dividend by the divisor. We guess that 21 fits into 136 around 6 times so we write that as the next digit in our result.
Taking the quotient from the last step we multiply it by the divisor. 6 x 21 = 126 which we write as the product.
Next up, we subtract the product from our current working dividend which in this case is 136 – 126 = 10 which we write as our remainder.
Finally we bring down the final digit or our original dividend (the 5 of 160.65) to form our new working dividend of 105.
Sub Problem 5
Nearly there and by now you should know the drill. Working dividend divided by the divisor gives us 105 / 21 = 5 which we take as our quotient and write as the next digit in our result.
Multiply our quotient by our divisor, 5 x 21 = 105 which we take as our product.
Subtract our product from the working dividend, 105 – 105 = 0 which we write as our remainder. As we have no more digits in our original dividend and have a remainder of zero we’re done. Looking above the line we therefore have our result. 160.65 / 21 = 7.65.
There are a couple of things to note about the division process I’ve outlined above.
- In the final step of the example above, if we had a remainder but no more digits in our original dividend, we would bring down an imaginary zero and continue the process until we had a remainder of zero or spotted a repeating pattern.
- If there is a decimal point in our original dividend, it will be located in the same position in our calculated result.
If your problem involves numbers that are signed, you should sort out the sign of your result according to the following rules:
If both the dividend and the divisor are positive our result will be positive.
If the dividend is negative but the divisor is positive, the result is negative.
If the dividend is positive but he divisor is negative the result is negative.
If the dividend and the divisor are both negative, the result will be positive.
Right, having got the hang of decimal long division, let’s take the process above and apply it to binary division.
The good news is that binary division is a lot easier than decimal division.
Instead of having to guess how many times our divisor fits into the working dividend (which can get complicated if the numbers involved are large), in binary division the answer will either be 0 or 1. This makes calculation far easier.
To illustrate the point, imagine we have the binary number 10010.001 and want to divide it by 11.1. Lets have a look at the steps.
Note: I’ve not shown all the intermediate stages this time but you should be able to follow along.
We start by writing out our problem. First, we check whether our divisor has a radix point which it has. To eliminate this, we move the radix point in both our dividend and divisor right by a single place and re-write our problem.
With the radix point eliminated in our divisor we are ready to go.
Sub Problems 1 – 3
I’ve collapsed the first three sub-problems into one as they are basically identical. In each, we follow the same four steps as we did with the decimal division example above. We take the first digit in our dividend and attempt to divide it by our divisor. In this case, it doesn’t fit so we write a 0 in the first column of our result, calculate the product (which is 0 and subtract it from our working dividend before bringing down the next digit of our original dividend to create a new working dividend. We repeat this process for the first three digits in our original dividend until eventually we reach the point where we have a working dividend of 1001.
Sub Problem 4
Back at step 1, we again attempt to divide our current working dividend (1001) by the divisor (111). This time, the divisor is less than the dividend and we write a 1 as the next digit in the result.
Moving on to step 2, we calculate the product 1 x 111 = 111 and then move to step 3.
Remember, step 3 is a subtraction operation. We learnt previously that we could perform subtraction by taking the two’s complement of the number we want to subtract and then add it instead.
Taking this approach, we calculate the two’s complement of 111 (remember the rules for two’s complement: flip all the bits and then add 1).
This gives us a two’s complement representation of 1001 which we then add to the current working dividend. Also remember how when we are adding a two’s complement number and we need to carry an additional bit into a new column we simply drop that bit. That is the case here. The result is a remainder of 100.
Step 4 sees us bring down the next bit in our original dividend to get a new working dividend of 100.
Sub Problem 5
Step 1 of sub-problem 5 sees us trying to divide our new working dividend of 100 by our divisor 111. As 111 is greater than 100 we put a zero as the next digit in our result. I’ll skip steps 2 and 3 (which basically have no effect) and then we bring down the next digit in the original dividend to get a new working dividend of 1000.
Sub Problem 6
In step 1 we divide our working dividend of 1000 by 111 which results in us writing a 1 as the next digit in our result. We then use the same two’s complement technique to subtract 111 from 1000. Again, we drop the carried bit and get a new remainder of 1. This is then combined with the next digit we bring down from the original dividend to create a new working dividend of 11.
Sub Problem 7 – 8
In sub-problem 7, we again go around the loop. This time, we attempt to divide our working dividend of 11 by our divisor 111. This results in 0 being added as the next digit or our result. We then perform the necessary multiplication and subtraction steps (which have no effect) and bring down the last and final digit in our original dividend to create a new working dividend of 111.
In our final sub problem, we follow the same process. This time we divide the working dividend of 111 by the divisor which is also 111. We write the quotient (1) as the next digit in the result and subtract the product of multiplying the quotient by our divisor (111) from our working dividend (111) to get a result of 0. With no remainder, and no more digits in our original dividend we have our final answer: 10010.001 / 11.1 = 101.01.
As you can see, division in binary is generally simpler than its decimal equivalent. In both cases, (decimal and binary) there are often a lot of smaller sub problems to solve but each of them is simply a matter of following the four step process we have discussed above:
- Bring Down
Hopefully by following through the examples above you will have got the hang of it. If not, be patient and give it a go yourself before referring back to my workings. Leave me a comment below if you need any help.
Image credit: http://flic.kr/p/5kqJEA