Binary Lesson 15 – Binary Division

📅 November 18, 2014

lesson15Binary division is an excellent way to practice an understanding of bits and binary values. Is one binary value larger than, smaller than, or equal to another?

This requires a good understanding of the binary place value system, and the better it is memorized, the easier binary division will be.

Also, binary division offers extensive practice with binary subtraction. We saved binary division until after we had introduced at least two methods for binary subtraction because the most involving part of binary division is the subtraction itself.

Sometimes, we must also add a radix point for values not easily divisible by the given number. If this happens, keep in mind that an exact value might not be possible, as in the case of irrational numbers, so it will be necessary to stop at a certain number of digits for a close approximation. The exact point at which this occurs will depend upon experience…or if your fingers get tired, or if you run out of pencil lead, or if you get lost in the seemingly endless series of zeros.

Division Process

The division process is the same as in decimal division, but think in binary.

1.  Will the current value divide into the first value? Is it less than or equal to the value?
2.  If yes, then record a 1 and subtract to find any remainder.
3.  If not, then proceed to the next bit to form a larger value to divide into. Add a radix point if necessary.

Let’s see how this works.

Divide 1010b by 10b.

In fractional form, this is written as,

1010   <-- dividend
----
 10    <-- divisor

1010b is the dividend, the number we divide into, and 10b is the divisor, the number we divide by. The result of division is called the quotient.

Write out the division problem as in decimal long division to help avoid mistakes.

   +-----------
10 | 1010

When dividing into 1010b, start with the number of bits in the divisor (two) and divide into the first two bits of the dividend from the left. Ask, “Is 10b less than or equal to 10b?”

If yes, record a 1. If not, record a 0. In this case the answer is yes, so record a 1. That is the first part of the answer. Record the 10b under the 10b and subtract.

      1
   +-----------
10 | 1010
   - 10
   --------
     00

10b – 10b equals nothing because the two values are equal. Now, we move to the third bit from the left, a 1. Bring it down to form 001b.

      1
   +-----------
10 | 1010
   - 10
   --------
     001

We will try to divide into this number. Ask, “Will 10b divide into 1b?” The answer is no. It’s too small, so we record a 0 over the third bit place in the quotient and progress to the fourth bit from the left. Bring it down to form 0010b.

 

       10
    +-----------
 10 | 1010
    - 10
   --------
      0010

 

With two bits to work with at this point, we divide 10b into 0010b (leading zeros can be ignored). 10b and 10b are equal values, so, yes, 10b will divide into 10b. We record a 1 over the fourth bit place from the left and subtract as before.

 

       101
    +-----------
 10 | 1010
    - 10
   --------
      0010
     -  10
    --------
        00

 

If the result of the last subtraction is 0, which it is here, then the division is complete and the divisor evenly divides into the dividend. No further division is possible. This will not always be the case, and some division operations will continue indefinitely due to the nature of irrational numbers.

In binary, 1010b divided by 10b equals 101b. We can convert the original problem to decimal and divide in decimal to confirm.

 

Binary           Decimal
-------------------------
1010b            10d <------- This is the decimal value "ten"
-----  = 101b    --- = 5d
 10b              2d

 

Fractional Division

We can divide binary fractions. The only difference is the setup.

Divide 10.11b by .010b.

      +-------
 .010 | 10.11

Like decimal division, we must remove the radix point from the divisor. The number of fractional places in the divisor tells us how many places to move the radix point (Include the trailing zeros in the fractional divisor when counting places). In this example, we move the radix point three places to the right since the divisor has three fractional places.

     +-------
 010 | 10.11

When we do this, we must also move the radix point the same number of places to the right in the dividend (three places). Append 0 bits as needed to fill the new places.

     +-------
 010 | 10110.  <-- radix point is now here

We can discard leading zeros from the divisor, so the result looks like this,

    +-------
 10 | 10110

Now, we are ready to divide. Division is the same as before. Take it two bits at a time since the divisor is two bits in length.

       1011
    +-------
 10 | 10110
    - 10
   ---------
      011
     - 10
    ------
      010

The binary fraction .010b divides evenly into 10.11b with a quotient of 1011b. We can convert to decimal to confirm.

10.11b   = 2.75d
  .010b  = 0.25d
     +--------
 .25 | 2.75

Move the decimal point two places to the right in both divisor and dividend:

    +------
 25 | 275

Divide:

       11
    +------
 25 | 275
    - 25
   --------
       25

2.75d / 0.25d = 11d. 11d converts to 1011d. Quotient is correct.

 

Irrational Division

Now, let’s try an irrational number. We will need to divide into fractional values and choose a location to terminate the quotient because it results in a repetend — a number pattern that repeats indefinitely.

Divide 1010b by 11b.

Converted to decimal, we are dividing 10d by 3d. This produces a quotient of 3.3333333… in decimal. The fractional 3 continues forever with each additional decimal place producing a quotient more precise, but it will never terminate in even division.

The same happens in binary. We can divide 1010b by 11b and add fractional binary places until the quotient is so close to even division that it is barely noticeable in real-world problems, but it will never divide evenly.

First, record the long division problem. This helps avoid mistakes.

    +---------
 11 | 1010

1) Will 11b divide into 10b? No, so we progress to the third bit place from the left. We could record leading zeros, but leading zeros are irrelevant, which is why we are ignoring them.

2) Will 11b divide into 101b? Yes! 11b (the divisor) is less than 101b, so it will divide into 101b. Maybe not evenly, but smaller numbers divide into larger numbers.

 

Sidenote: Greater Than or Less Than?

How do we know that 11b is less than 101b? Partly due to practice and familiarity with the binary system. Practice helps. A shortcut is to count the number of bits. For example, a 3-bit value (101b as seen here) will always be larger than a 2-bit value if its most significant bit is 1. Even if both bits in a 2-bit value are 11b, a 3-bit value is still greater if its most significant bit is 1. Therefore, 100b, 101b, 110b, and 111b are all greater than 11b, but 001b and 010b are not.

The same is true for larger bit lengths. For example, an 8-bit value whose most significant bit is 1 will be larger than any 7-bit value. 10000000b is greater than 1111111b.

 

Now that we know 11b divides into 101b, we record a 1 in the third bit place from the left and subtract 11b from 101b.

        1
    +---------
 11 | 1010
     - 11
     -----
       10

After subtraction, bring down the 0 from the fourth bit place from the left the same as in decimal division.

        1
    +---------
 11 | 1010
     - 11
      -----
       100

3) Will 11b divide into 100? Yes. Remember the shortcut described above? 100b is a 3-bit value whose most significant bit is set to 1, so it is greater than any 2-bit value. Record a 1 in the quotient for the fourth bit place, and subtract.

        11
    +---------
 11 | 1010
     - 11
     -----
       100
      - 11
     ------
         1

If we only a whole-number result, we would stop here. The result of 1010b divided by 11b         is 11b with a remainder of 1b/11b, but we want to obtain a few fractional values. Add a radix point immediately to the right of the fourth bit place from the left and append a 0 bit. Bring down the 0 bit.

        11.
    +---------
 11 | 1010.0
     - 11
     -----
       100
      - 11
    --------
         10

We continue dividing as before. When attempting to divide into the difference, pretend that the radix point does not exist. Ask, “Does 11b divide into 10b?” instead of asking “Does 11b divide into 1.0b?”

11b is greater than 10b, so it will divide into 10b. Record a 0 in the fifth bit place from the left.

        11.0
    +---------
 11 | 1010.0
      - 11
      -----
        100
       - 11
      --------
         10

Append another 0 bit and bring it down to form 100b.

        11.0
    +---------
 11 | 1010.00
      - 11
     -----
        100
       - 11
      --------
          100

Does 11b divide into 100b? Yes, so record a 1 over the sixth bit place and subtract.

        11.01
    +---------
 11 | 1010.00
      - 11
     -----
        100
       - 11
     --------
          100
         - 11
        ------
            1

We will continue for two more fractional places to see if a repetend occurs. Append a seventh 0 bit and bring it down.

        11.01
    +-----------
 11 | 1010.000
      - 11
      -----
         100
        - 11
       --------
           100
          - 11
         ------
             10

As before, check if 11b divides into 10b. No, so record a 0, append an eighth 0 bit, and bring it down.

        11.010
    +-----------
 11 | 1010.0000
     - 11
     -----
        100
       - 11
     --------
          100
         - 11
        ------
            100

11b does divide into 100b as before, so record a 1 and subtract.

        11.0101
    +-----------
 11 | 1010.0000
     - 11
     -----
        100
       - 11
      --------
          100
         - 11
        ------
            100
           - 11
           -----
              1

See the pattern? The binary fractional repetend is 01b, and it will continue forever because 1010b (10b) divided by 11b (3d) produces an irrational number. At this point, we choose to stop at four fractional bit places and settle on this quotient of 11.0101b.

If we convert 11.0101b to decimal we obtain the mixed number 3 and 5/16, or 3.3125, which is a close enough approximation of 3.33333…. This is the best we can do. Dividing to more fractional places will increase accuracy, but it will never produce an exact value. In this example, there will always be a remainder of 1/11b (1/3d, we are converting the numerator and denominator separately, not the entire fraction, to obtain 1/3d).

Practice

All of these problems can be solved on paper, so avoid using a calculator unless to perform binary/decimal conversions.

1. Divide 1010b by 10b

2. Divide 10.11b by .010b

3. Divide 1010b by 11b

4. Divide 11011b by 1b

5. Divide 1b by 11b. Stop at six fractional places.

6. Divide .0001b by .01b

7. (Ignore fractions) Without attempting to divide, will 1010b divide into 111b? Why?

8. (Ignore fractions) Without attempting to divide, will 0010b divide into 111b? Why?

9. Divide 11000000b by 100b. Convert to and divide in decimal first, and then perform the division in binary.  Check the binary quotient with the decimal quotient to verify the correct answer. (Conversion is necessary.)

10. Divide 10000000b by 1111111b. Check by converting to decimal. Stop at the seventh fractional place.

 

 

Answers

1. 101b

2. 1011b

3. 11.0101b with a remainder of 1/11b. 11.01b is also correct as well as something similar to 11.01010101b since an even quotient is not possible. The repetend is 01b no matter how many times it appears.

4. 11011b. Incredibly easy because we are dividing by 1. In this case, the dividend is the quotient.

5. .010101. This is the irrational number 0.3333333… when converted to decimal. It leads to the same issue as in problem #3 above. In decimal, it is 1/3. The key is to recognize that we need to add a radix point from the start to make division possible.

    +------
 11 | 1

11b will not divide into 1b, so we must enter the fractional territory. Add a radix point, and keep appending 0 bits until division is possible. Here is the full problem worked out:

       .010101
    +----------
 11 | 1.000000
      - 11
   ----------
         100
        - 11
       --------
           100
          - 11
         ------
             1

We stop at six places because the repetend will continue forever in this pattern.

 

6. .01b

     +----------
 .01 | .0001

First, remove the radix point from the divisor by moving it two places to the right. Move the radix point two places to the right in the dividend also.

        .
    +----------
 01 | 00.01

Remove the leading 0 from the divisor for simpler division.

       .
   +----------
 1 | 00.01

We are dividing by 1, so this is trivial to solve. Simply record the dividend as the quotient. No subtraction is necessary even though that works too.

     00.01
   +----------
 1 | 00.01

This is an exact answer. If we try to continue dividing, we will be doing nothing more than appending trailing zeros to the quotient which are discarded anyway.

 

7. No, because when the most significant bit of the 4-bit number is 1, it always be greater than any 3-bit number. This problem is practice with greater than/less than recognition.

 

8. Yes. Even though 0010b is a 4-bit number, its value is 2d, which divides into the 3-bit number 111b, which has a value of 7d. The 3-bit value is greater than the 4-bit value in this case, so, yes, 0010b will divide into 111b.

In real life, other factors, such as hardware limitations might restrict division of differing bit lengths, but for the sake of understanding the concept on paper, it works.

9. 110000b (48d)

11000000b = 192d
100b = 4d

Decimal:

192 / 4 = 48d

Binary:

         110000
     +-----------
 100 | 11000000

Convert and check: Does 110000b = 48d?

110000b = 32 + 16 + 0 + 0 + 0 + 0 = 48d

 

10. 1.0000001b. This problem is contrived to test attention and accuracy since it is easy to get lost in the sequence of zeros. It’s also much easier than it appears. In decimal, we are dividing 128 by 127, and this produces a never-ending string of digits (I stopped at 16 decimal places):

         1.0078740157480314
     +----------------------
 127 | 128.0000000000000000
     - 127
    ---------
         1 000
        -  889
       ---------
           1110
         - 1016
        ---------
             940
           - 889
          ------
              510
            - 508
          --------
               200
             - 127
           ---------
                730
              - 635
             ------
                 950
               - 889
              ------
                  610
                - 508
                ------
                  1020
                - 1016
              ---------
                    400
                  - 381
                  ------
                     190
                   - 127
                   ------
                      630
                    - 508
                   -------
                      122

Because of this, we cannot find an exact binary quotient, so we stop at the first binary fractional place where a 1 appears — the seventh binary fraction place.

If we convert 1.0000001b to decimal, we get 1.0078125d (1 + 1/128d). 127 * 1.0078125 = 127.9921875d, which is very close 128d, or 10000000b.

The repetend is .0000001b, so we could continue indefinitely (in theory, not actually checked) with 1.0000001000000100000010000001… repeating .0000001b for greater and greater precision but never exact. It is easy to get lost with division like this, but it makes for fun practice.

 

Even though manual binary division is probably something we will not use often, it is excellent practice that utilizes a number of binary skills, so devise your own problems for fun. Enjoy!

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: