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 0
10 10 10 10 10 10
d n 1 d 4 d3 d 2 d1 d 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 22 22
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
nyble = 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 2 3 4 5 6 7 8 9 A B C D E F
0 0 1 2 3 4 5 6 7 8 9 A B C D E F
1 1 2 3 4 5 6 7 8 9 A B C D E 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.
Notice that in binary, d 1  d, d 1  d
where d  {0,1}, we have: 0  1  0  1  1  0
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  100 2  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 2’s comp Sign-Mag
7 0111 0111
6 0110 0110
5 0101 0101
4 0100 0100
3 0011 0011
2 0010 0010
1 0001 0001
0 0000 0000 Pos 0

18
 Signed Numbers-4 bit example
Decimal 2’s comp Sign-Mag
-8 1000 N/A
-7 1001 1111
-6 1010 1110
-5 1011 1101
-4 1100 1100
-3 1101 1011
-2 1110 1010
-1 1111 1001
-0 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’s-
complement 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 0 1 0 0  (4)10
- 0 0 1 0  (2)10

0 1 0 0  (4)10
A+ (-B)
+ 1 1 1 0  (-2)10
10 0 1 0 2

“Throw this bit” away since n=4

27
Binary Subtraction - Example

B-A 0 0 1 0  (2)10
- 0 1 0 0  (4)10

0 0 1 0  (2)10
B + (-A)
+ 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

0101 (5)
+1100 (-4)
-------
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
39
n
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: 1564-1024 (210) = 540  n=10 or 1 in the (210)’s position
Subtract 512: 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: 12 – 8 (23) = 4  n=3 or 1 in (23)’s position
Subtract 4: 4 – 4 (22) = 0  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
2|_____ R=0 12
2|_____ R=0


391
2|_____ R=0 6
2|_____ R=0
195
2|_____ R=1 3
2|_____ R= 0
97
2|_____ R=1 1 R=1
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|_____ R = 12 = C
6
16|_____ R=1
0 R=6

N = 61C 16

46