Review on Number Systems Decimal, Binary, and Hexadecimal 1

Review on Number Systems Decimal, Binary, and Hexadecimal 1

Base-N Number System Base N N Digits: 0, 1, 2, 3, 4, 5, , N-1 Example: 1045N Positional Number System n 1 4 3 2 1 0 N N N N N N d n 1 d 4 d3 d 2 d1 d 0 Digit do is the least significant digit (LSD). Digit dn-1 is the most significant digit (MSD). 2

Decimal Number System Base 10 Ten Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Example: 104510 Positional Number System n 1 4 3 2 1 10 10 10 10 10 10 d n 1 d 4 d 3 d 2 d1 d 0 0 Digit d0 is the least significant digit (LSD). Digit dn-1 is the most significant digit (MSD). 3

Binary Number System Base 2 Two Digits: 0, 1 Example: 10101102 Positional Number System n 1 4 3 2 1 0 2 2 2 2 2 2 bn 1 b4 b3 b2 b1 b0 Binary Digits are called Bits Bit bo is the least significant bit (LSB). Bit bn-1 is the most significant bit (MSB). 4

Definitions nybble 4 bits byte 8 bits (short) word 2 bytes 16 bits (double) word 4 bytes 32 bits (long) word 8 bytes 64 bits 1K (kilo or “kibi”) 1,024 1M (mega or “mebi”) (1K)*(1K) 1,048,576 1G (giga or “gibi”) (1K)*(1M) 1,073,741,824 5

Hexadecimal Number System Base 16 Sixteen Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Example: EF5616 Positional Number System n 1 4 3 2 1 0 16 16 16 16 16 16 0000 0 0100 4 1000 8 1100 C 0001 1 0101 5 1001 9 1101 D 0010 2 0110 6 1010 A 1110 E 0011 3 0111 7 1011 B 1111 F 6

Binary Addition Single Bit Addition Table 0 0 0 0 1 1 1 0 1 1 1 10 Note “carry” 7

Hex Addition 4-bit Addition 4 4 8 4 8 C 8 7 F F E 1D Note “carry” 8

Hex Digit Addition Table 0 1 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 A A A B B B C C C D D D E E E F F F 10 2 2 3 4 5 6 7 8 9 A B C D E F 10 11 3 3 4 5 6 7 8 9 A B C D E F 10 11 12 4 4 5 6 7 8 9 A B C D E F 10 11 12 13 5 5 6 7 8 9 A B C D E F 10 11 12 13 14 6 6 7 8 9 A B C D E F 10 11 12 13 14 15 7 7 8 9 A B C D E F 10 11 12 13 14 15 16 8 8 9 A B C D E F 10 11 12 13 14 15 16 17 9 9 A B C D E F 10 11 12 13 14 15 16 17 18 A A B C D E F 10 11 12 13 14 15 16 17 18 19 B B C D E F 10 11 12 13 14 15 16 17 18 19 1A C C D E F 10 11 12 13 14 15 16 17 18 19 1A 1B D D E F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C E E F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D F F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 9

1’s Complements 1’s complement (or Ones’ Complement) To calculate the 1’s complement of a binary number just “flip” each bit of the original binary number. E.g. 0 1 , 1 0 01010100100 10101011011 10

Why choose 2’s complement? 11

2’s Complements 2’s complement To calculate the 2’s complement just calculate the 1’s complement, then add 1. 01010100100 10101011011 1 10101011100 Handy Trick: Leave all of the least significant 0’s and first 1 unchanged, and then “flip” the bits for all other digits. Eg: 01010100100 - 10101011100 12

Complements Note the 2’s complement of the 2’s complement is just the original number N EX: let N 01010100100 (2’s comp of N) M 10101011100 (2’s comp of M) 01010100100 N 13

Two’s Complement Representation for Signed Numbers Let’s introduce a notation for negative digits: For any digit d, define d d. d 1 d , d 1 d Notice that in binary, 0 1 0 1 1 0 where d {0,1}, we have: Two’s complement notation: 1 1 1 1 0 1 To encode a negative number, we implicitly negate the leftmost (most significant) bit: E.g., 1000 ( 1)000 1·23 0·22 0·21 0·20 8 14

Negating in Two’s Complement Theorem: To negate ( X YZ ) X YZ 1 2 2 a two’s complement number, just complement it and add 1. Proof (for the case of 3-bit numbers XYZ): ( X YZ 2 ) X YZ 2 X YZ 2 ( X 1)YZ 2 XYZ 2 1002 XYZ 112 1 X (Y 1)( Z 1) 2 1 X YZ 2 1 15

Signed Binary Numbers Two methods: First method: sign-magnitude Use one bit to represent the sign 0 positive, 1 negative Remaining bits are used to represent the magnitude Range - (2n-1 – 1) to 2n-1 - 1 where n number of digits Example: Let n 4: Range is –7 to 7 or 1111 to 0111 16

Signed Binary Numbers Second method: Two’s-complement Use the 2’s complement of N to represent -N Note: MSB is 0 if positive and 1 if negative Range - 2n-1 to 2n-1 -1 where n number of digits Example: Let n 4: Range is –8 to 7 Or 1000 to 0111 17

Signed Numbers – 4-bit example Decimal 7 6 5 4 3 2 1 0 2’s comp 0111 0110 0101 0100 0011 0010 0001 0000 Sign-Mag 0111 0110 0101 0100 0011 0010 0001 0000 Pos 0 18

Signed Numbers-4 bit example Decimal -8 -7 -6 -5 -4 -3 -2 -1 -0 2’s comp Sign-Mag 1000 N/A 1001 1111 1010 1110 1011 1101 1100 1100 1101 1011 1110 1010 1111 1001 0000 ( 0) 1000 19

Signed Numbers-8 bit example 20

Notes: “Humans” normally use sign-magnitude representation for signed numbers Eg: Positive numbers: N or N Negative numbers: -N Computers generally use two’s-complement representation for signed numbers First bit still indicates positive or negative. If the number is negative, take 2’s complement to determine its magnitude Or, just add up the values of bits at their positions, remembering that the first bit is implicitly negative. 21

Examples Let N 4: two’s-complement What is the decimal equivalent of 01012 Since MSB is 0, number is positive 01012 4 1 510 What is the decimal equivalent of 11012 Since MSB is one, number is negative Must calculate its 2’s complement 11012 (0010 1) 00112 or 310 22

Very Important!!! – Unless otherwise stated, assume two’scomplement numbers for all problems, quizzes, HW’s, etc. The first digit will not necessarily be explicitly underlined. 23

Arithmetic Subtraction Borrow Method This is the technique you learned in grade school For binary numbers, we have 0 - 0 0 1 - 0 1 1 - 1 0 1 0 - 1 1 with a “borrow” 24

Binary Subtraction Note: A – ( B) A (-B) A – (-B) A (-(-B)) A ( B) In other words, we can “subtract” B from A by “adding” –B to A. However, -B is just the 2’s complement of B, so to perform subtraction, we 1. Calculate the 2’s complement of B 2. Add A (-B) 25

Binary Subtraction - Example Let n 4, A 01002 (410), and B 00102 (210) Let’s find A B, A-B and B-A A B 0 1 0 0 (4)10 0 0 1 0 (2)10 0 11 0 6 26

Binary Subtraction - Example A-B A (-B) 0 1 0 0 (4)10 - 0 0 1 0 (2)10 0 1 0 0 (4)10 1 1 1 0 (-2)10 10 0 1 0 2 “Throw this bit” away since n 4 27

Binary Subtraction - Example B-A B (-A) 0 0 1 0 (2)10 - 0 1 0 0 (4)10 0 0 1 0 (2)10 1 1 0 0 (-4)10 1110 -2 1 1 1 02 - 0 0 1 02 -210 28

“16’s Complement” method The 16’s complement of a 16 bit Hexadecimal number is just: 1000016 – N16 Q: What is the decimal equivalent of B2CE16 ? 29

16’s Complement Since sign bit is one, number is negative. Must calculate the 16’s complement to find magnitude. 1000016 – B2CE16 ? We have 10000 - B2CE 30

16’s Complement FFF10 - B2CE 4 D3 2 31

16’s Complement So, 1000016 – B2CE16 4D3216 4 4,096 13 256 3 16 2 19,76210 Thus, B2CE16 (in signed-magnitude) represents -19,76210. 32

Why does 2’s complement work? 33

Sign Extension 34

Sign Extension Assume a signed binary system Let A 0101 (4 bits) and B 010 (3 bits) What is A B? To add these two values we need A and B to be of the same bit width. Do we truncate A to 3 bits or add an additional bit to B? 35

Sign Extension A 0101 and B 010 Can’t truncate A! Why? A: 0101 - 101 But 0101 101 in a signed system 0101 5 101 -3 36

Sign Extension Must “sign extend” B, so B becomes 010 - 0010 Note: Value of B remains the same So 0101 (5) 0010 (2) Sign bit is extended -------0111 (7) 37

Sign Extension What about negative numbers? Let A 0101 and B 100 Now B 100 1100 Sign bit is extended (5) (-4) 0101 1100 ------10001 (1) Throw away 38

Why does sign extension work? Note that: ( 1) 1 11 111 1111 111 1 Thus, any number of leading 1’s is equivalent, so long as the leftmost one of them is implicitly negative. Proof: 111 1 (111 1) (100 0 11 1) (1) So, the combined value of any sequence of leading ones is always just 1 times the position value of the rightmost 1 in the sequence. 111 100 0 ( 1)·2n n 39

Number Conversions 40

Decimal to Binary Conversion Method I: Use repeated subtraction. Subtract largest power of 2, then next largest, etc. Powers of 2: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2n Exponent: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , n 20 21 22 23 24 25 26 27 28 29 210 2n 41

Decimal to Binary Conversion Suppose x 156410 Subtract 1024: Subtract 512: 1564-1024 (210) 540 n 10 or 1 in the (210)’s position 540-512 (29) 28 n 9 or 1 in the (29)’s position 28 256, 27 128, 26 64, 25 32 28, so we have 0 in all of these positions Subtract 16: 28-16 (24) 12 n 4 or 1 in (24)’s position Subtract 8: Subtract 4: 12 – 8 (23) 4 4 – 4 (22) 0 n 3 or 1 in (23)’s position n 2 or 1 in (22)’s position Thus: 156410 (1 1 0 0 0 0 1 1 1 0 0)2 42

Decimal to Binary Conversion Method II: Use repeated division by radix. 2 1564 2 24 782 R 0 2 12 R 0 2 391 R 0 2 6 R 0 2 3 R 0 195 R 1 2 2 1 R 1 97 R 1 2 2 2 48 R 1 0 R 1 24 R 0 Collect remainders in reverse order 11000011100 43

Binary to Hex Conversion 1. Divide binary number into 4-bit groups 01 1 0 0 0 0 1 1 1 0 0 Pad with 0’s If unsigned number 2. Substitute hex digit for each group Pad with sign bit if signed number 61C16 44

Hexadecimal to Binary Conversion Example 1. Convert each hex digit to equivalent binary (1 E 9 C)16 (0001 1110 1001 1100)2 45

Decimal to Hex Conversion Method II: Use repeated division by radix. 16 1564 97 16 6 16 0 R 12 C R 1 R 6 N 61C 16 46