Associated Topics || Dr. Math Home || Search Dr. Math

### Long Division in Binary

Date: 06/06/2000 at 18:26:50
From: Itti Jindani
Subject: Binary Mathematics

What is the algorithm for binary division? Kindly explain using some
examples, 33 / 3 (i.e. 100001 / 11) and 33 / 4 (i.e. 100001 / 100).

Date: 06/15/2000 at 11:04:57
From: Doctor TWE
Subject: Re: Binary Mathematics

Hi Itti - thanks for writing to Dr. Math.

You can use the same algorithm as long division in decimal, but the
values will go in either one time or 0 times.

Let's do your example: 100001/11 (33/3 in decimal).

First, we write it in "long-division form":

_________
11 ) 100001

Since 11 has two bits (digits), we look at the first two bits of
100001. Can 11 go into 10...? No, so we move one digit to the right.
Can 11 go into 100...? Yes, exactly once. So we put a 1 in the
quotient above the 100, subtract, and carry down the next bit. We now
have:

____1____
11 ) 100001
11
-----
10

Note that we have to do some borrowing to do the subtraction. If
you're not familiar with binary subtraction, look at the following
pages from our archives:

Binary Subtraction
http://mathforum.org/dr.math/problems/houston.7.25.96.html

Complement of a Number
http://mathforum.org/dr.math/problems/steve.7.10.96.html

Moving one place over, can 11 go into 10? No, so we record a 0 in the
quotient and carry down the next bit:

____10___
11 ) 100001
11
-----
100

Moving over another place, can 11 go into 100? Yes, so we record a 1
in the quotient, subtract, and carry down the next bit:

____101__
11 ) 100001
11
-----
100
11
----
11

One last time, we move over another place. Can 11 go into 11? Again,
the answer is yes, so we record another 1 and subtract:

____1011_
11 ) 100001
11
-----
100
11
----
11
---
0

Since the result of the subtraction is zero, we're done and we have an
exact answer: 100001/11 = 1011 (33/3 = 11 in decimal).

If the number is not a whole number, we can add a "radix point." This
is the equivalent of a decimal point, but of course we don't call it
a "decimal" point in other bases.

For your second example, 100001/100 (33/4 in decimal), we do it
similarly for the whole number
portion, like so:

___1000_
100 ) 100001
100
------
0001

(Note that I carried down a 0 twice, then a 1 in the final place.) Now
I have a choice of how I can represent the answer:

In "Quotient/Remainder" form:  1000 r 1    (8 r 1 decimal)
In "Fractional" form:          1000 1/100  (8 1/4 decimal)

Or I can continue the division and represent the answer in radix form.
I put a radix point in the divisor and the quotient, and add trailing
zeroes. Then I continue and carry down the next digit:

___1000.____
100 ) 100001.000
100
----------
0001 0

Can 100 go into 10? (Note that I ignore the radix point when
determining whether 100 goes into 10 - just as in a decimal division
with a fractional part.) No, so I carry down the next digit:

___1000.0___
100 ) 100001.000
100
----------
0001 00

Can 100 go into 100? Yes, so I subtract (note that I also ignore the
radix point when doing the subtraction):

___1000.01__
100 ) 100001.000
100
----------
0001 00
1 00
----
0

Since the result of the subtraction is zero, we can stop and we have
an exact answer: 100001/100 = 1000.01 (33/8 = 8.25 in decimal.)
This is the third form of the answer:

In "Quotient/Remainder" form:  1000 r 1    (8 r 1 decimal)
In "Fractional" form:          1000 1/100  (8 1/4 decimal)
In "radix" form:               1000.01     (8.25 decimal)

Just as with decimal, some values won't divide evenly, and we'll get a
repeating fractional part. We can stop at any time, but realize that
we've only found an approximation, not an exact value.

One final note: If the dividend (the 100 in this example) had a radix
point in it, move the radix points in BOTH the dividend and divisor to
the right an equal number of places sufficient to remove it from the
divisor. For example, to divide 11001.1 by 11.001, first move the
radix points right 3 places (you'll have to add zeroes to the
dividend). Then divide 11001100 by 11001.

For some more examples and explanations in our archives, look at:

Binary Operations
http://mathforum.org/dr.math/problems/matt4.7.97.html

Multiplying and Dividing Computer Style
http://mathforum.org/dr.math/problems/hodsdon9.8.98.html

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
http://mathforum.org/dr.math/

Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search