Lecture 4b:Binary ArithmeticCS105: Great Insights in Computer ScienceMichael L. Littman, Fall 2006Subtraction• As in decimal, proceed right to left, borrowing if not doing so would force us to subtract a bigger number from a smaller one.100100101-10110010110110101100111Overflow• When working with numbers made of a fixed number of bits, carries can “overflow”, meaning we might not be able to represent the full sum. Example (8 bits):01010011+10110010(1)00000101Negation• Overflow provides an interesting way to think of negation.• Recall in algebra, an additive inverse of x is the number y such that x+y = 0. So, y = -x.100000000-010100111010110101111111110101101+01010011(1)00000000Two’s Complement• To find the negation of a number, flip all the bits, then add one:0101001110101100+000000011010110183 172 = 255!83 173 = 256!83 = “!83”Subtraction as Negate/Add• Combining these ideas, we can subtract one number from another by taking the two’s complement and adding!Multiplication• Of course, multiplication can be carried out by repeated addition, but it’s a very inefficient way to go with big numbers.• Our standard grade-school approach to multiplication carries forward to binary numbers as well.Multiplication• Boils down to:• copy, shift, add10101101x 0101001110101101101011010101011010000+10101101
View Full Document
Unlocking...