Binary Division and Negative Binary Numbers

Date: 02/24/2002 at 00:14:14
From: Marc Payne
Subject: Binary Division and Negative Binary Numbers

Hi.

I am a beginner computer programmer trying to learn how a computer 
actually deals with numbers. My C++ programming class has not been 
sufficient, so I have spent several months studying on my own time 
trying to grasp all the concepts. I know how to add binary numbers, 
multiply them, and to an extent, subtract them, but some areas still 
bother me.

For example, suppose you entered 11111000 into a binary calculator.  
How would it know whether that is to be used as 248 or -8? 

My other questions are about division. How does the computer begin 
the division process? What does it do when it cannot right shift the 
bits?  Does it ever simply repeatedly subtract?  How does it deal with 
a non-integer result, other than by truncating it?

Thank you for your help,
Marc Payne

Date: 02/24/2002 at 03:38:07
From: Doctor Twe
Subject: Re: Binary Division and Negative Binary Numbers

Hi Marc - thanks for writing to Dr. Math.

First, let me point you to our "Number Bases" FAQ at:

   http://mathforum.org/dr.math/faq/faq.bases.html   

It sounds as if you already know most of what's in it, but it has some 
links that you might find helpful.

>For example, suppose you entered 11111000 into a binary calculator.  
>How would it know whether that is to be used as 248 or -8? 

The simple answer is, the adder circuit doesn't know or care - to it, 
the value is just 11111000, no more, no less. The arithmetic and logic 
operations work the same way whether the values are unsigned binary or 
twos-complement signed binary. It is up to the _decoder_ (the user, 
the decoder circuit, or the decoder program) to interpret the result. 
The value may not even be a number - it may be an ASCII character 
code, an HTML color value, or a sound byte.

For example, suppose your (8-bit) binary calculator were to add 
11111000 + 11110110. The adder circuit simply adds:

       1 111
         11111000
     +   11110110
         --------
       1 11101110

To the adder circuit, the answer is simply 11101110. Note that the 9th 
bit is usually not treated as part of the answer, but rather stored 
separately as a "carry out."

Now if these were to be treated as unsigned binary, we'd interpret the 
problem as:

         11111000     248
     +   11110110   + 246
         --------     ---
       1 11101110     238

The presence of the carry out (9th bit) would indicate that our result 
is invalid - the correct answer is beyond the range of 8-bit unsigned 
binary numbers.

If, on the other hand, these were to be treated as twos-complement 
signed binary, we'd interpret the problem as:

         11111000     (- 8)
     +   11110110   + (-10)
         --------     ----
       1 11101110     (-18)

In this case, the carry out is meaningless. To check whether the 
answer is valid, we'd look for an "overflow" condition. An overflow is 
generated by checking the MSb's (8th bits) of the values. If in the 
MSb's we get:

       0...          1...
     + 0...   or   + 1...
       ----          ----
       1...          0...

Then we have an "overflow" and the result is invalid as 
twos-complement signed binary. The correct answer would be out of 
range for 8-bit signed binary.


>My other questions are about division. How does the computer begin 
>the division process?  What does it do when it cannot right shift the 
>bits?  Does it ever simply repeatedly subtract?  How does it deal 
>with a non-integer result, other than by truncating it?

Let me first point you to two entries in our Ask Dr. Math archives 
that explain how the long division algorithm works in binary:

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

   Long Division in Binary
   http://mathforum.org/dr.math/problems/jindani.6.6.00.html   

Next, let me suggest an archive entry that explains how to represent 
fractions in binary (non-computer style):

   Converting to Binary
   http://mathforum.org/dr.math/problems/maya.05.27.01.html   

Finally, let me indicate some archive entries that explain how 
computers represent and use non-integer, or "floating point" numbers:

   Fixed Point and Floating Point Numbers
   http://mathforum.org/dr.math/problems/huband.5.19.00.html   

   Definition of Floating Point Data
   http://mathforum.org/dr.math/problems/judy.07.02.01.html   

   Floating-Point Binary Fractions
   http://mathforum.org/dr.math/problems/mairaj.7.19.99.html   

The last one also has some links to other Web sites that have more 
details on floating point numbers' use in computers. Read these, then 
if you have any more questions, write back!

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

Date: 02/24/2002 at 11:39:26
From: Marc Payne
Subject: Binary Division and Negative Binary Numbers

Thank you very much!

I am finally beginning to understand binary operations. Although I 
probably will not need them often during my life, I find it very 
satisfying to know how computers and calculators actually operate.

Marc Payne