Binary arithmetic lecture cs0710a08 20112009edit

CE713A Computer and Graphics Architectures Computer Arithmetic* Dr C Süheyl Özveren: 

CE713A Computer and Graphics Architectures Computer Arithmetic * Dr C Süheyl Özveren * Collated from various resources including the internet strictly for self study guidelines

Binary Addition And Subtraction Facts: 

2 Binary Addition And Subtraction Facts Subtraction 0 - 0 = 0 1 - 0 = 1 1 - 1 = 0 0 – 1 = 1 with borrow 1 from next column Addition 0 + 0 = 0 1 + 0 = 1 1 + 1 = 0 with a carry of 1 1 + 1 + 1= 1 with a carry of 1 1 1 1 + 1 + 1 11 10 3 2

Binary Addition: 

3 Binary Addition Binary addition is very simple. This is best shown in an example of adding two binary numbers… 1 1 1 1 0 1 + 1 0 1 1 1 -------------------- 0 1 0 1 1 1 1 1 1 1 1 0 0 carries

Binary Subtraction: 

4 Binary Subtraction We can also perform subtraction (with borrows in place of carries). Let’s subtract (10111) from (1001101) 1 1 1 1 0 1 1 0 0 - 1 0 0 1 1 1 ------------------------ 0 0 0 1 0 1 borrows

Binary Multiplication: 

5 Binary Multiplication Binary multiplication is much the same as decimal multiplication, except that the multiplication operations are much simpler… 1 0 1 1 1 X 1 0 1 0 ----------------------- 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 ----------------------- 1 1 1 0 0 1 1 0

How To Represent Signed Numbers: 

6 How To Represent Signed Numbers Plus and minus sign used for decimal numbers: 25 (or +25), -16, etc. For computers, desirable to represent everything as bits . Three types of signed binary number representations: signed magnitude , 1’s complement , 2’s complement . In each case: left-most bit indicates sign: positive (0) or negative (1). Consider signed magnitude : 0 0001100 2 = 12 10 Sign bit Magnitude 1 0001100 2 = -12 10 Sign bit Magnitude

One’s Complement Representation: 

7 One’s Complement Representation The one’s complement of a binary number involves inverting all bits. 1’s comp of 00110011 is 11001100 1’s comp of 10101010 is 01010101 For an n bit number N the 1’s complement is (2 n -1) – N. To find negative of 1’s complement number take the 1’s complement . 0 0001100 2 = 12 10 Sign bit Magnitude 1 1110011 2 = -12 10 Sign bit Magnitude

Slide 8: 

8 Ones Complement Subtraction implemented by addition & 1's complement Still two representations of 0! This causes some problems Some complexities in addition

Two’s Complement Representation: 

9 Two’s Complement Representation The two’s complement of a binary number involves inverting all bits and adding 1. 2’s comp of 00110011 is 11001101 2’s comp of 10101010 is 01010110 For an n bit number N the 2’s complement is (2 n -1) – N + 1. To find negative of 2’s complement number take the 2’s complement. 0 0001100 2 = 12 10 Sign bit Magnitude 1 1110100 2 = -12 10 Sign bit Magnitude

Two’s Complement: 

10 Two’s Complement Only one representation for 0 One more negative number than positive number like 1's comp except shifted one position clockwise

Two’s Complement Shortcuts: 

11 Two’s Complement Shortcuts Algorithm 1 – simply complement each bit and then add 1 to the result. Finding the 2’s complement of (01100101)2 and of its 2’s complement… N = 01100101 [n] = 10011011. 10011010 01100100. + 1 + 1. --------------- ---------------. 10011011 01100101. Algorithm 2 – starting with the least significant bit, copy all of the bits up to and including the first 1 bit and then complementing the remaining bits. Eg1. N = 0 1 1 0 0 1 0 1 eg2. N = 0 1 1 0 0 1 0 0. [N] = 1 0 0 1 1 0 1 1 [n] = 1 0 0 1 1 1 0 0.

Finite Number Representation: 

12 Finite Number Representation Machines that use 2’s complement arithmetic can represent integers in the range. -2 n-1 <= N <= 2 n-1 -1. Where n is the number of bits available for representing N. Note that. 2 n-1 -1 = (011..11) and –2 n-1 = (100..00). For 2’s complement more negative numbers than positive. For 1’s complement two representations for zero. For an n bit number in base (radix) z there are z n different unsigned values. (0, 1, …z n-1 ).

1’s Complement Addition: 

13 1’s Complement Addition Using 1’s complement numbers, adding numbers is easy. For example, suppose we wish to add +(1100)2 and +(0001)2. Let’s compute (12) + (1). (12) = +(1100) = 01100 in 1’s comp. (1) = +(0001) = 00001 in 1’s comp. 0 1 1 0 0 + 0 0 0 0 1 -------------- 0 0 1 1 0 1 0 -------------- 0 1 1 0 1 Add carry Final Result Step 1: Add binary numbers Step 2: Add carry to lower-order bit Add

1’s Complement Subtraction: 

14 1’s Complement Subtraction Using 1’s complement numbers, subtracting numbers is also easy. For example, suppose we wish to subtract +(0001) from +(1100). Let’s compute (12) - (1). (12) = +(1100) = 01100 in 1’s comp. (-1) = -(0001) = 11110 in 1’s comp. 0 1 1 0 0 - 0 0 0 0 1 -------------- 0 1 1 0 0 + 1 1 1 1 0 -------------- 1 0 1 0 1 0 1 -------------- 0 1 0 1 1 Add carry Final Result Step 1: Take 1’s complement of 2nd operand Step 2: Add binary numbers Step 3: Add carry to low order bit 1’s comp Add

2’s Complement Addition: 

15 2’s Complement Addition Using 2’s complement numbers, adding numbers is easy. For example, suppose we wish to add +(1100)2 and +(0001)2. Let’s compute (12) + (1). (12) = +(1100) = 01100 in 2’s comp. (1) = +(0001) = 00001 in 2’s comp. 0 1 1 0 0 + 0 0 0 0 1 -------------- 0 0 1 1 0 1 Step 1: Add binary numbers Step 2: Ignore carry bit Ignore

2’s Complement Subtraction: 

16 2’s Complement Subtraction Using 2’s complement numbers, follow steps for subtraction. For example, suppose we wish to subtract +(0001) from +(1100). Let’s compute (12) - (1). (12) = +(1100) = 01100 in 2’s comp. (-1) = -(0001) = 11111 in 2’s comp. 0 1 1 0 0 - 0 0 0 0 1 -------------- 0 1 1 0 0 + 1 1 1 1 1 -------------- 1 0 1 0 1 1 Step 1: Take 2’s complement of 2nd operand Step 2: Add binary numbers Step 3: Ignore carry bit 2’s comp Add Ignore Carry

Summary: 

17 Summary Digital systems surround us. Inside computers. Inside huge variety of other electronic devices (embedded systems). Digital systems use 0s and 1s. Encoding analog signals to digital can provide many benefits. E.G., Audio -- higher-quality storage/transmission, compression, etc. Encoding integers as 0s and 1s: binary numbers. Signed numbers represented in signed magnitude, 1’s complement, and 2’s complement. 2’s complement most important (only 1 representation for zero). Important to understand treatment of sign bit for 1’s and 2’s complement.

Attendance Sheet: 

Attendance Sheet On line binary addition Other Applets

Self Study: 

19 Self Study Binary System link 1 Binary System link 2 Number systems Binary Arithmetic 2’s Complement Becoming Bitwise Basic Arithmetic in C / C++

the wonder of numbers: 

20 the wonder of numbers 12 345 679 1x 9 = 111 111 111 12 345 679 2x 9 = 222 222 222 12 345 679 3x 9 = 333 333 333 12 345 679 4x 9 = 444 444 444 12 345 679 5x 9 = 555 555 555 12 345 679 6x 9 = 666 666 666 12 345 679 7x 9 = 777 777 777 12 345 679 8x 9 = 888 888 888 12 345 679 9x 9 = 999 999 999 12 345 679 x 999 999 999 = 12 345 678 987 654 321

Slide 22: 

22 How Much Compute Power Is There? Hans Moravec: http://www.frc.ri.cmu.edu/~hpm/talks/revo.slides/power.aug.curve/power.aug.gif

Slide 23: 

23 How Much Compute Power Does It Take? From Hans Moravec, Robot Mere Machine to Transcendent Mind 1998.

Comparison Of Representations: 

24 Comparison Of Representations Easiness of negative conversion S + M > 1’s Complement > 2’s Complement Hardware S+M: Needs an adder and a subtractor for Addition 1’s and 2’s Complement: Need only an adder Speed of Arithmetic 2’s Complement > 1’s Complement(end-around C) Recognition of Zero 2’s Complement is fast Fixed Point Representations

Information Representation: 

25 Information Representation N bits can represent up to 2 N values. Examples: 2 bits  represent up to 4 values (00, 01, 10, 11). 3 bits  rep. Up to 8 values (000, 001, 010, …, 110, 111). 4 bits  rep. Up to 16 values (0000, 0001, 0010, …., 1111). To represent M values, log 2 m bits are required. Examples: 32 values  requires 5 bits. 64 values  requires 6 bits. 1024 values  requires 10 bits. 40 values  how many bits? 100 values  how many bits?

Negative Numbers: 

26 Negative Numbers Unsigned numbers: only non-negative values. Signed numbers: include all values (positive and negative). There are 3 common representations for signed binary numbers: Sign-and-magnitude. 1s complement. 2s complement.

Sign-and-magnitude (1/3): 

27 Sign-and-magnitude (1/3) The sign is represented by a ‘sign bit.’ 0 for +. 1 for -. E.G.: A 1-bit sign and 7-bit magnitude format. sign magnitude 00110100  +110100 2 = +52 10 10010011  -10011 2 = -19 10

Sign-and-magnitude (2/3): 

28 Sign-and-magnitude (2/3) Largest value: 01111111 = +127 10 Smallest value: 11111111 = -127 10 Zeros: 00000000 = +0 10 10000000 = -0 10 Range: -127 10 to +127 10 Question: For an n -bit sign-and-magnitude representation, what is the range of values that can be represented?

Sign-and-magnitude (3/3): 

29 Sign-and-magnitude (3/3) To negate a number, just invert the sign bit. Examples: How to negate 00100001 sm (decimal 33)? Answer: 10100001 sm (decimal -33). How to negate 10000101 sm (decimal -5)? Answer: 00000101 sm (decimal +5).

1s COMPLEMENT (1/3): 

30 1s COMPLEMENT (1/3) Given a number x which can be expressed as an n -bit binary number, its negated value can be obtained in 1s-complement representation using: - X = 2 n – x – 1 Example: with an 8-bit number 00001100 (or 12 10 ), its negated value expressed in 1s-complement is: -00001100 2 = 2 8 – 12 – 1 (calculation in decimal) = 243 = 11110011 1s (This means that -12 10 is written as 11110011 in 1s-complement representation.)

1s COMPLEMENT (2/3): 

31 1s COMPLEMENT (2/3) Essential technique to negate a value: invert all the bits . Largest value: 01111111 = +127 10. Smallest value: 10000000 = -127 10. Zeros: 00000000 = +0 10 11111111 = -0 10. Range: -127 10 to +127 10. The most significant (left-most) bit still represents the sign: 0 for positive; 1 for negative.

1s COMPLEMENT (3/3): 

32 1s COMPLEMENT (3/3) Examples (assuming 8-bit numbers): (14) 10 = (00001110) 2 = (00001110) 1s -(14) 10 = -(00001110) 2 = (11110001) 1s -(80) 10 = -( ? ) 2 = ( ? ) 1s

2s COMPLEMENT (1/3): 

33 2s COMPLEMENT (1/3) Given a number x which can be expressed as an n -bit binary number, its negated value can be obtained in 2s-complement representation using: - X = 2 n – x Example: with an 8-bit number 00001100 (or 12 10 ), its negated value expressed in 1s-complement is: -00001100 2 = 2 8 – 12 (calculation in decimal) = 244 = 11110100 2s (This means that -12 10 is written as 11110100 in 2s-complement representation.)

2s COMPLEMENT (2/3): 

34 2s COMPLEMENT (2/3) Essential technique to negate a value: invert all the bits , then add 1 . Largest value: 01111111 = +127 10. Smallest value: 10000000 = -128 10. Zero: 00000000 = +0 10. Range: -128 10 to +127 10. The most significant (left-most) bit still represents the sign: 0 for positive; 1 for negative.

2s COMPLEMENT (3/3): 

35 2s COMPLEMENT (3/3) Examples (assuming 8-bit numbers): (14) 10 = (00001110) 2 = (00001110) 2s -(14) 10 = -(00001110) 2 = (11110010) 2s -(80) 10 = -( ? ) 2 = ( ? ) 2s Compare with slide 30.

How To Represent Negative Numbers?: 

36 How To Represent Negative Numbers? So far, un signed numbers Obvious solution: define leftmost bit to be sign! 0  +, 1  - Rest of bits can be numerical value of number Representation called sign and magnitude MIPS uses 32-bit integers. +1 ten would be: 0 000 0000 0000 0000 0000 0000 0000 0001 And –1 ten in sign and magnitude would be: 1 000 0000 0000 0000 0000 0000 0000 0001

Adding Binary Numbers: 

37 Adding Binary Numbers For individual bits there are only four possibilities: 0 0 1 1 + 0 + 1 + 0 + 1 0 1 1 10

Adding Binary Numbers: 

38 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 11100101 + 1011101

Adding Binary Numbers: 

39 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos. 1 11100101 + 1011101 0

Adding Binary Numbers: 

40 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 11100101 + 1011101 10

Adding Binary Numbers: 

41 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 11100101 + 1011101 010

Adding Binary Numbers: 

42 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 1 11100101 + 1011101 0010

Adding Binary Numbers: 

43 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 1 1 11100101 + 1011101 00010

Adding Binary Numbers: 

44 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 1 1 1 11100101 + 1011101 000010

Adding Binary Numbers: 

45 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 1 1 1 1 11100101 + 1011101 1000010

Adding Binary Numbers: 

46 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 1 1 1 1 1 1 1 11100101 + 1011101 101000010

Adding Binary Numbers: 

47 Adding Binary Numbers For multiple digits we do the same as in base-10: we add corresponding bits and carry the twos: 11100101  229 + 1011101  + 93 101000010  322

Adding Binary Numbers: 

48 Adding Binary Numbers But that only works for unsigned numbers. (Positive numbers). For signed numbers it's much more complicated.

Limitations Of Representations: 

49 Limitations Of Representations None of these number representations acts exactly like the integers. Infinitely many integers, but only 2 N binary numbers for a specific N-bit representation. That means some operations will overflow. If the program doesn't crash when that happens, it will simply produce wrong answers (which is worse!).

Binary Numbers: Addition & Multiplication: 

50 Binary Numbers: Addition & Multiplication Examples: 1001100b 1110b + 1101011b * 1101b 10110101b 111101b + 1101101b * 1111b 10110111 10110110 100100010 1110010011

Complementary Arithmetic: 

51 Complementary Arithmetic 1’s complement Switch all 0’s to 1’s and 1’s to 0’s Binary # 10110011 1’s complement 01001100

Arithmetic: Two’s Complement: 

52 Arithmetic: Two’s Complement 1 101 b (signed binary number) 0010 b (reverse all bits) + 1 0011 b (unsigned value = 3) - 3d = One’s complement Two’s complement two’s complement of n = NOT(n) +1

Complementary Arithmetic: 

53 Complementary Arithmetic 2’s complement Step 1: find 1’s complement of the number Binary # 11000110 1’s complement 00111001 Step 2: add 1 to the 1’s complement 00111001 + 00000001 00111010

Arithmetic: Signed Numbers: 

54 Arithmetic: Signed Numbers Signed numbers: the number of bits must be fixed. In every case, the highest bit is the sign bit. 0 means + 1 means - Example: Unsigned number: 1101b = 13 Signed number: 1101b = ?

Signed Magnitude Numbers: 

55 Signed Magnitude Numbers Sign bit 0 = positive 1 = negative 31 bits for magnitude This is your basic Integer format 110010.. …00101110010101

Arithmetic: Range Of Signed Numbers: 

56 Arithmetic: Range Of Signed Numbers Two's complement: sizes signed byte: -128 to +127 = 2 7 - 1 signed word: -32,768 to +32,767 = 2 15 - 1 singed double word: -2,147,483,648 to +2,147,483,647 = 2 31 - 1 Comments: There is one more negative than positive value There are (about) half as many positive signed values as unsigned values

Arithmetic: Addition & Subtraction (Signed): 

57 Arithmetic: Addition & Subtraction (Signed) Algorithm to add in signed decimal. (Sign and magnitude) if both numbers have the same sign add the two magnitudes prefix with the common sign else subtract the number with smaller magnitude from the number with the larger magnitude prefix with the sign of the number with the larger magnitude.

Arithmetic: Addition & Subtraction (Signed): 

58 Arithmetic: Addition & Subtraction (Signed) Two's complement : add two numbers including their sign bits discard any carry out of the sign position Addition + 6 0 0 0 0 0 1 1 0 + 13 0 0 0 0 1 1 0 1 + 19 0 0 0 1 0 0 1 1 Example: - 19 1 1 1 0 1 1 0 1 - 6 1 1 1 1 1 0 1 0 - 13 1 1 1 1 0 0 1 1

Slide 59: 

59 Arithmetic: Addition & Subtraction (signed) Example: 6 0 0 0 0 0 1 1 0 - 13 - 7 1 1 1 1 1 0 0 1 Subtraction Take the 2’s complement of the subtrahend (including the sign bit) Add it to the minuend (including the sign bit) - 6 13 0 0 0 0 1 1 0 1 + 7 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0

Arithmetic: Signed Numbers: 

60 Arithmetic: Signed Numbers Signed numbers: the number of bits must be fixed. In every case, the highest bit is the sign bit. 0 means + 1 means - Example: Unsigned number: 1101b = 13 Signed number: 1101b = ?

Arithmetic: Two’s Complement: 

61 Arithmetic: Two’s Complement 1 101 b (signed binary number) 0010 b (reverse all bits) + 1 0011 b (unsigned value = 3) - 3d = One’s complement Two’s complement two’s complement of n = NOT(n) +1 reversible

Arithmetic: Range Of Signed Numbers: 

62 Arithmetic: Range Of Signed Numbers Two's complement : sizes signed byte: -128 to +127 = 2 7 - 1 signed word: -32,768 to +32,767 = 2 15 - 1 singed double word: -2,147,483,648 to +2,147,483,647 = 2 31 - 1 Comments : There is one more negative than positive value There are (about) half as many positive signed values as unsigned values

Negative Numbers.: 

63 Negative Numbers. Easiest, use most significant bit to represent sign thus. 0 means positive and 1 means negative. However it messes up arithmetic add two, 4 bit numbers +1 and -3. Instead we use a trick of binary 2’s complement , Consider an 8 bit number. Positive numbers which require only 7 bits are represented as normal. Negative number, magnitude is complemented and then 1 is added. Thus +23D = 0001 0111. And -23D = 1110 1000 + 1 = 1110 1001. Add 7 and 32 and then separately add 6 and -10 to prove it . No need to subtract in binary, just make subtrahend into negative addend and then add to augend. Note that there are limitations to the effectiveness of 2’s complement arithmetic due to the word size of computer and the operands.

Slide 65: 

65 How Much Compute Power is There? Hans Moravec: http://www.frc.ri.cmu.edu/~hpm/talks/revo.slides/power.aug.curve/power.aug.gif

Slide 66: 

66 How Much Compute Power Does it Take? From Hans Moravec, Robot Mere Machine to Transcendent Mind 1998.

See You Next Week: 

67 See You Next Week 12 345 679 1x 9 = 111 111 111 12 345 679 2x 9 = 222 222 222 12 345 679 3x 9 = 333 333 333 12 345 679 4x 9 = 444 444 444 12 345 679 5x 9 = 555 555 555 12 345 679 6x 9 = 666 666 666 12 345 679 7x 9 = 777 777 777 12 345 679 8x 9 = 888 888 888 12 345 679 9x 9 = 999 999 999 12 345 679 x 999 999 999 = 12 345 678 987 654 321