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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.