Binary numbers and arithmetic.ppt

1、Binary numbers and arithmetic,addition,Addition (decimal),Addition (binary),Addition (binary),Addition (binary),So can we count in binary?,Counting in binary (4 bits),0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0000 0001 ,multiplication,Multiplication (decimal),Multiplication (binary),Multiplication (bina

2、ry),Its interesting to note that binary multiplication is a sequence of shifts and adds of the first term (depending on the bits in the second term.,110100 is missing here because the corresponding bit in the second terms is 0.,Representing signed (positive and negative) numbers,Representing numbers

3、 (ints),Fixed, finite number of bits.bits bytes C/C+ Intel Sun 8 1 char sbyte byte 16 2 short sword half 32 4 int or long sdword word 64 8 long long sqword xword,Representing numbers (ints),Fixed, finite number of bits.bits Intel signed unsigned 8 sbyte -27+27-1 0+28-1 16 sword -215+215-1 0+216-1 32

4、 sdword -231+231-1 0+232-1 64 sqword -263+263-1 0+264-1In general, for k bits, the unsigned range is 0+2k-1 and the signed range is -2k-1+2k-1-1.,Methods for representing signed ints.,signed magnitude1s complement (diminished radix complement)2s complement (radix complement)excess bD-1,Signed magnit

5、ude,Ex. 4-bit signed magnitude 1 bit for sign 3 bits for magnitude,Signed magnitude,Ex. 4-bit signed magnitude 1 bit for sign 3 bits for magnitude,1s complement (diminished radix complement),Let x be a non-negative number. Then x is represented by bD-1+(-x) where b = base D = (total) # of bits (incl

6、uding the sign bit)Ex. Let b=2 and D=4. Then -1 is represented by 24-1-1 = 1410 or 11102.,1s complement (diminished radix complement),Let x be a non-negative number. Then x is represented by bD-1+(-x) where b = base & D = (total) # of bits (including the sign bit) Ex. What is the 9s complement of 12

7、38910? Given b=10 and D=5. Then the 9s complement of 12389 = 105 1 12389 = 100000 1 12389 = 99999 12389 = 87610,1s complement (diminished radix complement),Let x be a non-negative number. Then x is represented by bD-1+(-x) where b = base D = (total) # of bits (including the sign bit) Shortcut for ba

8、se 2? All combinations used, but 2 zeros!,2s complement (radix complement),Let x be a non-negative number. Then x is represented by bD+(-x). Ex. Let b=2 and D=4. Then -1 is represented by 24-1 = 15 or 11112. Ex. Let b=2 and D=4. Then -5 is represented by 24 5 = 11 or 10112. Ex. Let b=10 and D=5. The

9、n the 10s complement of 12389 = 105 12389 = 100000 12389 = 87611.,2s complement (radix complement),Let x be a non-negative number. Then x is represented by bD+(-x). Ex. Let b=2 and D=4. Then -1 is represented by 24-1 = 15 or 11112. Ex. Let b=2 and D=4. Then -5 is represented by 24 5 = 11 or 10112. S

10、hortcut for base 2?,2s complement (radix complement),Shortcut for base 2? Yes! Flip the bits and add 1.,2s complement (radix complement),Are all combinations of 4 bits used? No. (Now we only have one zero.) 1000 is missing! What is 1000? Is it positive or negative? Does -8 + 1 = -7 work in 2s comple

11、ment?,excess bD-1 (biased representation),For pos, neg, and 0, x is represented bybD-1 + xEx. Let b=2 and D=4. Then the excess 8 (24-1) representation for 0 is 8+0 = 8 or 10002.Ex. Let b=2 and D=4. Then excess 8 for -1 is 8 1 = 7 or 01112.,excess bD-1,For pos, neg, and 0, x is represented by bD-1 +

12、x. Ex. Let b=2 and D=4. Then the excess 8 (24-1) representation for 0 is 8+0 = 8 or 10002. Ex. Let b=2 and D=4. Then excess 8 for -1 is 8 1 = 7 or 01112.,2s complement vs. excess bD-1,In 2s, positives start with 0; in excess, positives start with 1.Both have one zero (positive).Remaining bits are th

13、e same.,Summary of methods for representing signed ints.,1000=-8| 0000 unused,Binary arithmetic,Signed magnitude 1s complement 2s complement Excess K (biased),Binary Arithmetic,Signed magnitude,Addition w/ signed magnitude algorithm,For A - B, change the sign of B and perform addition of A + (-B) (a

14、s in the next step) For A + B: if (Asign=Bsign) then R = |A| + |B|; Rsign = Asign; else if (|A|B|) then R = |A| - |B|; Rsign = Asign; else if (|A|=|B|) then R = 0; Rsign = 0; else R = |B| - |A|; Rsign = Bsign; Complicated?,Binary Arithmetic,2s complement,Representing numbers (ints) using 2s compleme

15、nt,Fixed, finite number of bits.bits Intel signed 8 sbyte -27+27-1 16 sword -215+215-1 32 sdword -231+231-1 64 sqword -263+263-1In general, for k bits, the signed range is -2k-1+2k-1-1. So where does the extra negative value come from?,Representing numbers (ints),Fixed, finite number of bits.bits In

16、tel signed 8 sbyte -27+27-1 16 sword -215+215-1 32 sdword -231+231-1 64 sqword -263+263-1In general, for k bits, the signed range is -2k-1+2k-1-1. So where does the extra negative value come from?,Addition of 2s complement binary numbers,Consider 8-bit 2s complement binary numbers. Then the msb (bit

17、 7) is the sign bit. If this bit is 0, then this is a positive number; if this bit is 1, then this is a negative number. Addition of 2 positive numbers. Ex. 40 + 58 = 98,Addition of 2s complement binary numbers,Consider 8-bit 2s complement binary numbers. Addition of a negative to a positive.What ar

18、e the values of these 2 terms? -88 and 122 -88 + 122 = 34,So how can we perform subtraction?,Addition of 2s complement binary numbers,Consider 8-bit 2s complement binary numbers. Subtraction is nothing but addition of the 2s complement. Ex. 58 40 = 58 + (-40) = 18,discard carry,Carry vs. overflow,Ad

19、dition of 2s complement binary numbers,Carry vs. overflow when adding A + B If A and B are of opposite sign, then overflow cannot occur.If A and B are of the same sign but the result is of the opposite sign, then overflow has occurred (and the answer is therefore incorrect).Overflow occurs iff the c

20、arry into the sign bit differs from the carry out of the sign bit.,Addition of 2s complement binary numbers,class test public static void main ( String args )byte A = 127;byte B = 127;byte result = (byte)(A + B);System.out.println( “A + B = “+ result ); ,#include int main ( int argc, char* argv ) ch

21、ar A = 127;char B = 127;char result = (char)(A + B);printf( “A + B = %d n“, result );return 0; ,Result = -2 in both Java (left) and C+ (right). Why?,Addition of 2s complement binary numbers,class test public static void main ( String args )byte A = 127;byte B = 127;byte result = (byte)(A + B);System

22、out.println( “A + B = “+ result ); ,Result = -2 in both Java and C+. Why? Whats 127 as a 2s complement binary number?What is 111111102? Flip the bits: 00000001. Then add 1: 00000010. This is -2.,Binary Arithmetic,1s complement,Addition with 1s complement,Note: 1s complement has two 0s! 1s complemen

23、t addition is tricky (end-around-carry).,8-bit 1s complement addition,Ex. Let X = A816 and Y = 8616. Calculate Y - X using 1s complement.,8-bit 1s complement addition,Ex. Let X = A816 and Y = 8616. Calculate Y - X using 1s complement.Y = 1000 01102 = -12110X = 1010 10002 = -8710X = 0101 01112(Note:

24、C=0 out of msb.),Y - X = -121 + 87 = -34 (base 10),8-bit 1s complement addition,Ex. Let X = A816 and Y = 8616. Calculate X - Y using 1s complement.,8-bit 1s complement addition,Ex. Let X = A816 and Y = 8616. Calculate X - Y using 1s complement.X = 1010 10002 = -8710Y = 1000 01102 = -12110Y = 0111 10

25、012(Note: C=1 out of msb.),X - Y = -87 + 121 = 34 (base 10),end around carry,Binary Arithmetic,Excess K (biased),Binary arithmetic and Excess K (biased),Method: Simply add and then flip the sign bit. -1 0111 +5 1101 - - +4 0100 - flip sign - 1100+1 1001 -5 0011 - - -4 1100 - flip sign - 0100+1 1001 +5 1101 - - +6 0110 - flip sign - 1110-1 0111 -5 0011 - - -6 1010 - toggle sign - 0010,(Not used for integer arithmetic but employed in IEEE 754 floating point standard.),