Binary Division

This is the fourth of a four part series on “pencil and paper” binary arithmetic, which I’ve written as a supplement to my binary calculator. The first article discusses binary addition; the second article discusses binary subtraction; the third article discusses binary multiplication; this article discusses binary division.

The pencil-and-paper method of binary division is the same as the pencil-and-paper method of decimal division, except that binary numerals are manipulated instead. As it turns out though, binary division is simpler. There is no need to guess and then check intermediate quotients; they are either 0 are 1, and are easy to determine by sight.

Decimal Division

Pencil-and-paper division, also known as long division, is the hardest of the four arithmetic algorithms. Like the other algorithms, it requires you to solve smaller subproblems of the same type. But unlike the other algorithms, there is no limited set of “facts” that solve all possible subproblems. Solving these division subproblems requires estimation, guessing, and checking. In addition to these division subproblems, multiplication and subtraction are required as well.

Let’s review how decimal division is done, so that we can set the stage for how division is done in binary. Here is an example:

The algorithm is a series of steps, each step having these four substeps:

1. Divide: Divide the working portion of the dividend by the divisor. (The dividend is the number under the line.)
2. Multiply: Multiply the quotient (a single digit) by the divisor.
3. Subtract: Subtract the product from the working portion of the dividend. (I don’t write down minus signs — they’re implied.)
4. Bring down: Copy down the next digit of the dividend to form the new working portion.

Here’s the example again, step-by-step:

• Step 0

  Does 88 go into 8? No, because it’s greater than 8. Does 88 go into 83? No, because it’s greater than 83. Does 88 go into 831? Yes, because it’s less than or equal to 831.

  (The first step of long division, as commonly practiced, combines several steps and their substeps into one. That’s why I call this step 0. Technically, 88 goes into 8 zero times, so we should write down a 0, multiply 88 by 0, subtract 0 from 8, and then bring down the 3. Next, we should write down a 0 because 88 goes into 83 zero times, multiply 88 by 0, subtract 0 from 83, and bring down the 1. We’re just eliminating a bunch of stuff that produces superfluous leading zeros.)

• Step 1
  1. Divide: Does 88 go into 831? (Yes, we already know that from step 0.) How many times does it go in? 9 times. (Normally you have to guess the answer and do the multiplication and subtraction to verify you guessed correctly; I’ll just show the correct answer, to keep things from getting too messy.)
  2. Multiply: 9 x 88 = 792. (If 9 were a guess, your first check is to see if 792 is less than 831. It is, so so far, so good.)
  3. Subtract: 831 – 792 = 39. (If 9 were a guess, your second check is to see if 39 is less than 88. It is, so your guess was correct. Actually, in this case, this has to check out, since we can’t go higher than 9.)
  4. Bring down: Bring down the 2 to make 392.
• Step 2
  1. Divide: Does 88 go into 392? Yes, 4 times.
  2. Multiply: 4 x 88 = 352.
  3. Subtract: 392 – 352 = 40.
  4. Bring down: Bring down the implied trailing 0 to make 400.
• Step 3
  1. Divide: Does 88 go into 400? Yes, 4 times.
  2. Multiply: 4 x 88 = 352.
  3. Subtract: 400 – 352 = 48.
  4. Bring down: Bring down the implied trailing 0 to make 480.
• Step 4
  1. Divide: Does 88 go into 480? Yes, 5 times.
  2. Multiply: 5 x 88 = 440.
  3. Subtract: 480 – 440 = 40.
  4. Bring down: Bring down the implied trailing 0 to make 400.
• Step 5

  Stop the presses! We tried to divide 400 by 88 before — two steps ago. That means we have a two-digit cycle (45) from here on out. The answer is 9.445.

The red digits are the carries that occur during the multiplication substeps (the multiplication is done as if the divisor — the bigger number — is on top, by convention). Each red digit is crossed out before the next multiplication. To avoid clutter, I have chosen not to mark the borrows that occur during subtraction.

I Picked The Hardest Type of Example

My example has a multi-digit divisor, and has an answer with a remainder that I wrote as a repeating decimal. I wanted one example that showed long division to its fullest. I could have picked a problem with a single-digit divisor (which would require no guessing, assuming you know the multiplication facts), or one that produced an integer quotient, or one that produced a quotient with a fractional part that terminated. I could have expressed the fractional part as an integer remainder, or in fraction form.

Other Cases

• If the divisor or dividend is negative, you can remove the signs and apply the appropriate sign to the answer at the end.
• If the divisor has a decimal point, shift the decimal point right until the divisor is an integer, and shift the dividend by the same number of places.
• If the divisor is greater than the dividend, just proceed with the algorithm as is. Trailing zeros will be brought down to form the appropriate subproblems.

Binary Division

Let’s return to the example of the introduction, 1011.11/11. Here it is broken down into steps, following the same algorithm I used for decimal numbers:

• Step 0

  Does 11 go into 1? No, because it’s greater than 1. Does 11 go into 10? No, because it’s greater than 10. Does 11 go into 101? Yes, because it’s less than or equal to 101. (Remember, these are binary numerals; pronounce them “one-one”, “one-zero”, “one-zero-one”, etc.)

• Step 1
  1. Divide: Does 11 go into 101? (Yes, we already know that from step 0.) How many times does it go in? One time. There is no guessing. It’s easy to see 11 is less than 101, so we know it goes in. And if it goes in, it goes in only once.
  2. Multiply: 1 x 11 = 11. (Remember how simple it is to “multiply” a binary number by a single digit — just copy the number down if that single digit is 1, or write down 0 if that single digit is 0.)
  3. Subtract: 101 – 11 = 10.
  4. Bring down: Bring down the 1 to make 101.
• Step 2
  1. Divide: Does 11 go into 101? Yes, 1 time.
  2. Multiply: 1 x 11 = 11.
  3. Subtract: 101 – 11 = 10.
  4. Bring down: Bring down the 1 to make 101.
• Step 3
  1. Divide: Does 11 go into 101? Yes, 1 time.
  2. Multiply: 1 x 11 = 11.
  3. Subtract: 101 – 11 = 10.
  4. Bring down: Bring down the 1 to make 101.
• Step 4
  1. Divide: Does 11 go into 101? Yes, 1 time.
  2. Multiply: 1 x 11 = 11.
  3. Subtract: 101 – 11 = 10.
  4. Bring down: Bring down the 0 to make 100.
• Step 5
  1. Divide: Does 11 go into 100? Yes, 1 time.
  2. Multiply: 1 x 11 = 11.
  3. Subtract: 100 – 11 = 1.
  4. Bring down: Bring down the 0 to make 10.
• Step 6
  1. Divide: Does 11 go into 10? No (write down a 0).
  2. Multiply: (We don’t need to record this step; we’re just going to get 0.)
  3. Subtract: (We don’t need to record this step; we’re just going to get 10.)
  4. Bring down: Bring down the 0 to make 100.
• Step 7

  We stop here, recognizing that we divided 100 by 11 two steps ago. This means we have a two-digit cycle (10) from here on out. The quotient is 11.1110.

Checking the Answer

When the answer has a repeating fractional part, checking it is not as straightforward as it is for the other arithmetic operations. What we can do is approximate the quotient to a finite number of places and then check that it comes close to the expected answer.

You can check the answer in a few ways. One way is by doing binary multiplication by hand: you verify that the approximated quotient (11.11101011, for example) multiplied by the divisor (11) equals the dividend (1011.11). (I’ll leave that as an exercise, but the answer is 1011.11000001, which is very close to 1011.11).

Another way to check is to convert the operands to decimal, do decimal division, and then convert the approximate decimal answer to binary. 1011.11 = 11.75, and 11 = 3. 11.75/3 = 3.916. Estimating that as 3.91666666666666667, for example, my binary converter says it equals 11.111010101010101010101010101010101010 when truncated to 36 places. That looks like it wants to be 11.1110, the answer we got using binary division.

You can also check the answer using my binary calculator. It says 1011.11/11 is 11.111010101010 (to 12 places, for example). Again, that looks like 11.1110.

If you want to verify the repeating part directly, you can use this conversion tool; here’s what to enter:

• Initial Base: 2
• Integral part: 11
• Non-Repeating Fractional Part: 11
• Repeating Fractional Part: 10
• New Base: 10

It gives the decimal answer we expect: 3.916. (Actually, the more direct way to use this tool is to enter ‘2’ for ‘New Base’; this gives the fraction 101111/1100, which is equivalent to our division problem of 1011.11/11.)

You can also use this tool to convert in the opposite direction, verifying that 3.916 converts to 11.1110.

(There are also analytical ways to check the answer exactly: read my articles about the subtraction method, the direct method, and the series method.)

Discussion

Like the other arithmetic algorithms, I described the division algorithm in a base-independent way. I wanted to stress the mechanical procedure, not why it works (in either decimal or binary).

When you do binary long division, you might find yourself doing some of the substeps in your head in decimal (e.g., 101 – 11 is 5 – 3 = 2, which is 10 in binary).

Although binary division is easier than decimal division (because there’s no guessing and effectively no multiplication), you will find that always having the same number (the divisor) as the subtrahend will produce a pattern that will start mesmerizing you; it’s easy to get lost in that sea of 1s and 0s. (Be thankful my example only had a two-digit repeating cycle!)

If you play around with binary division you’ll see that it produces more repeating fractional numbers than decimal division does. For example, 2/5 = 0.4, but 10/101 = 0.0110.

Further Reading

There are many explanations of binary division on the Web; one that I like in particular, and that comes closest to what I’ve explained, is Dr. Math’s “Long Division in Binary.”