CSE111 Fall 2008 H Kershner Binary Arithmetic Negative numbers and Subtraction Binary Mathematics Binary Addition this is performed using the same rules as decimal except all numbers are limited to combinations of zeros 0 and ones 1 Using 8 bit numbers 1 11 0000 11102 0000 01102 0001 01002 which is which is 1410 610 2010 Not all integers are positive What about negative numbers What if we wanted to do So 1410 210 1210 1410 210 1210 1410 210 1210 1410 210 1210 This example is a deceptively easy because while there no need to borrow Let s look at another example 1 13 12310 1910 10410 If we are using a paper and pencil binary subtraction can be done using the same principles as decimal subtraction Binary Subtraction Use standard mathematical rules 0000 11102 0000 01102 0000 10002 which is which is 1410 610 810 This is rather straightforward In fact no borrowing was even required in this example Copyright 2008 by Helene G Kershner CSE111 Fall 2008 H Kershner Try this example 1 0 10 10 10 0001 10012 0000 11102 0000 10112 2510 1410 1110 THIS WAS PAINFUL When so much borrowing is involved the problem is very error prone Not only was the example above complex because of all the borrowing required but computers have additional problems with signed or negative numbers Given the nature of the machine itself how do we represent a negative number What makes this even worse is that computers are fixed length or finiteprecision machines There are two common ways to represent negative numbers within the computer Remember the minus sign does not exist The computer world is made up entirely of zeros 0 and ones 1 These two techniques are called signed magnitude representation and two s complement Let s explore sign magnitude representation first In the sign magnitude number system the most significant bit the leftmost bit holds the sign positive or negative A zero 0 in that leftmost bit means the number is positive A one 1 in that leftmost bit means the number is negative Step 1 Decide how many bits the computer has available for your operations Remember computers are fixed length or finite precision machines For example if we use 4 bits the leftmost bit is the sign bit and all the rest are used to hold the binary numbers In a 4 bit computer world this leaves only 3 bits to hold the number This limits our numbers to only very small ones XXXX the left most bit is considered the sign bit This is the sign bit Using four bits these are the ONLY binary numbers a computer could represent A 4 bit number would look like 0 1 2 3 4 5 6 7 0000 0001 0010 0011 0100 0101 0110 0111 1 2 3 4 5 6 7 1001 1010 1011 1100 1101 1110 1111 If we were using 8 bits the left most bit will contain the sign This would leave 7 bits to hold the number XXXX XXXX This is the sign bit Copyright 2008 by Helene G Kershner CSE111 Fall 2008 H Kershner This sign bit is reserved and is no longer one of the digits that make up the binary number Remember if the sign bit is zero 0 the binary number following it is positive If the sign bit is one 1 the binary number following it is negative Using the sign magnitude system the largest positive number that can be stored by an 8 bit computer is 0 Sign 1 1 1 64 32 16 1 1 1 1 8 4 2 1 12710 This is 64 32 16 8 4 2 1 12710 If there were a one 1 in the first bit the number would be equal to 12710 1 Sign 1 1 1 64 32 16 1 1 1 1 8 4 2 1 12710 Over time it has become obvious that a system that even further reduces the number of available bits while meaningful is not especially useful Then of course there is still the problem of how to deal with these positive and negative numbers While this representation is simple arithmetic is suddenly impossible The standard rules of arithmetic don t apply Creating a whole new way to perform arithmetic isn t overly realistic Fortunately another technique is available Two s Complement Two s complement is an alternative way of representing negative binary numbers This alternative coding system also has the unique property that subtraction or the addition of a negative number can be performed using addition hardware Architects of early computers were thus able to build arithmetic and logic units that performed operations of addition and subtraction using only adder hardware As it turns out since multiplication is just successive addition and division is just successive subtraction it was possible to use simple adder hardware to perform all of these operations Let s look at an example 1410 610 1410 610 810 0000 11102 1000 01102 2 left most digit is 0 number is positive left most digit is 1 number is negative Step 1 Decide how many bits you are going to use for all your operations For our purposes we will always use 8 bits If we were using 8 bits the left most bit will contain the sign This would leave 7 bits to hold the number XXXX XXXX This is the sign bit Copyright 2008 by Helene G Kershner CSE111 Fall 2008 H Kershner This sign bit is reserved and is no longer one of the digits that make up the binary number Using two s complement the computer recognizes the presence of a one 1 in the leftmost bit which tells the machine that before it does mathematics it needs to convert negative numbers into their two s compliment equivalent 0000 11102 the sign bit is 0 so the number is positive The binary number is 7 digits long 1000 01102 the sign bit is 1 so the number is negative The binary number is only 7 digits long Example 1 1410 610 1410 610 810 0000 11102 1000 01102 2 left most digit is 0 number is positive left most digit is 1 number is negative Step 2 Strip the sign bits off the numbers Step 3 Convert the negative number into it s two s complement form Note If neither of the number were negative we would be doing simple addition and this would not be necessary How do we find the two s complement of 6 Write down the number without the sign bit a Flip all the digits 000 01102 111 10012 1 The 1 0 the 0 1 b Add 1 to this number c This is now 6 in the two s complement format 111 10102 Step 4 Add the two s complement in place of the negative number So 1410 610 810 000 11102 111 10102 in two s complement format 1 000 1000 this is the positive number 8 in binary Overflow bit IGNORE IT Worked Copyright 2008 by Helene G Kershner CSE111 Fall 2008 H Kershner Example 2 1210 910 310 Or 1210 910 …