ch3a-binary-numbers.ppt ch3a-binary-numbers.ppt ch3a-binary-numbers.ppt

i am as a student making ppt on number system!

1. 1
Review on Number Systems
Decimal, Binary, and Hexadecimal

2. 2
Base-N Number System
Base N
N Digits: 0, 1, 2, 3, 4, 5, …, N-1
Example: 1045
N
Positional Number System

•Digit d
o is the least significant digit (LSD).
•Digit d
n-1 is the most significant digit (MSD).1 4 3 2 1 0
1 4 3 2 1 0
n
n
N N N N N N
d d d d d d



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

4. 4
Binary Number System
Base 2
Two Digits: 0, 1
Example: 1010110
2
Positional Number System
Binary Digitsare called Bits
Bit b
ois the least significant bit (LSB).
Bit b
n-1is the most significant bit (MSB).1 4 3 2 1 0
1 4 3 2 1 0
2 2 2 2 2 2
n
n
b b b b b b



5. 5
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

6. 6
Hexadecimal Number System
Base 16
Sixteen Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Example: EF56
16
Positional Number System

00000
00011
00102
00113
01004
01015
01106
01117
10008
10019
1010A
1011B
1100C
1101D
1110E
1111F1 4 3 2 1 0
16 16 16 16 1616
n

7. 7
Binary Addition
•Single Bit Addition Table
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10Note “carry”

8. 8
Hex Addition
•4-bit Addition
4 + 4 = 8
4 + 8 = C
8 + 7 = F
F + E = 1DNote “carry”

9. 9
Hex Digit Addition Table
+0123456789ABCDEF
00123456789ABCDEF
1123456789ABCDEF10
223456789ABCDEF1011
33456789ABCDEF101112
4456789ABCDEF10111213
556789ABCDEF1011121314
66789ABCDEF101112131415
7789ABCDEF10111213141516
889ABCDEF1011121314151617
99ABCDEF101112131415161718
AABCDEF10111213141516171819
BBCDEF101112131415161718191A
CCDEF101112131415161718191A1B
DDEF101112131415161718191A1B1C
EEF101112131415161718191A1B1C1D
FF101112131415161718191A1B1C1D1E

10. 10
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

11. 11
Why choose 2’s complement?

12. 12
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

13. 13
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

14. 14
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,
where d{0,1}, we have:
Two’s complement notation:
To encode a negative number, we implicitly
negatethe leftmost(most significant) bit:
E.g., 1000 = (−1)000
= −1·2
3
+ 0·2
2
+ 0·2
1
+ 0·2
0
= −8 101111
011010
1,1


 dddd

15. 15
Negating in Two’s Complement
Theorem: To negate
a two’s complement
number, just complement it and add 1.
Proof(for the case of 3-bit numbers XYZ):1)(
22  YZXYZX 1
1)1)(1(
111100
)1()(
2
2
222
22
2
2




YZX
ZYX
YZXYZX
YZXYZXYZXYZX

16. 16
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 -(2
n-1
–1) to 2
n-1
-1
where n=number of digits
Example: Let n=4: Range is –7 to 7 or
1111 to 0111

17. 17
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 -2
n-1
to 2
n-1
-1
where n=number of digits
Example: Let n=4: Range is –8 to 7
Or 1000 to 0111

18. 18
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

19. 19
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

20. 20
Signed Numbers-8 bit example

21. 21
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.

22. 22
Examples
Let N=4: two’s-complement
What is the decimal equivalent of
0101
2
Since MSB is 0, number is positive
0101
2 = 4+1 = +5
10
What is the decimal equivalent of
1101
2 =
Since MSB is one, number is negative
Must calculate its 2’s complement
1101
2 = −(0010+1)= −0011
2 or −3
10

23. 23
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.

24. 24
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
0 -1 = 1with a “borrow”
1

25. 25
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)

26. 26
Binary Subtraction -Example
Let n=4, A=0100
2(4
10), and
B=0010
2 (2
10)
Let’s find A+B, A-B and B-A
0 1 0 0
+ 0 0 1 0
(4)
10
(2)
10
0 11 0 6
A+B

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

28. 28
Binary Subtraction -Example
0 0 1 0
-0 1 0 0
(2)
10
(4)
10
1 1 1 0 -2
B-A
0 0 1 0
+ 1 1 0 0
(2)
10
(-4)
10
B + (-A)
1 1 1 0
2= -0 0 1 0
2= -2
10

29. 29
“16’s Complement” method
The 16’s complement of a 16 bit
Hexadecimal number is just:
=10000
16 –N
16
Q: What is the decimal equivalent of
B2CE
16 ?

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

31. 31
16’s Complement
FFF
1
0
-B2CE
23D4

32. 32
16’s Complement
So,
10000
16 –B2CE
16 = 4D32
16
= 4×4,096 + 13×256 + 3×16 + 2
= 19,762
10
Thus, B2CE
16(in signed-magnitude)
represents -19,762
10.

33. 33
Why does 2’s complement
work?

34. 34
Sign Extension

35. 35
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?

36. 36
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

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

38. 38
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

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

40. 40
Number Conversions

41. 41
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, 2
n
Exponent:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , n
2
10
2
n
2
9
2
8
2
0
2
7
2
1
2
2
2
3
2
6
2
4
2
5

42. 42
Decimal to Binary Conversion
Suppose x = 1564
10
Subtract 1024: 1564-1024 (2
10
) = 540 n=10 or 1 in the (2
10
)’s position
Thus:
1564
10= (1 1 0 0 0 0 1 1 1 0 0)
2
Subtract 512:540-512 (2
9
) = 28 n=9 or 1 in the (2
9
)’s position
Subtract 16: 28-16 (2
4
)= 12 n=4 or 1 in (2
4
)’s position
Subtract 8:12 –8 (2
3
)= 4 n=3 or 1 in (2
3
)’s position
Subtract 4:4 –4 (2
2
)= 0 n=2 or 1 in (2
2
)’s position
2
8
=256, 2
7
=128, 2
6
=64, 2
5
=32 > 28, so we have 0 in all of these positions

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

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

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

46. 46
Decimal to Hex Conversion
Method II:
Use repeated division by radix.
16 | 1564
97 R = 12 = C16|_____
6 R = 116|_____
0 R = 6
N = 61C
16