CS 114: Discrete Structures
CHAPTER 4:
MACHINE LEVEL REPRESENTATION OF DATA
Outline
Number systems.
Numeric data representation.
Decimal Numbers
Binary Numbers
Octal Numbers
Hexadecimal Numbers
Conversion between different numbering System
Arithmetic Operations in Binary System
Signed and Unsigned numbers
Addition
Subtraction using 2’s Complement
Overflow
Floating point representation
2
Number Systems
Number systems can be categorized into: Decimal Roman
2 II
1. Non-Positional Number System 20 XX
• Symbol represents the value regardless of its position. 200 CC
• Example: Roman numbers: I, II, III, IV, V, VI, VII, VIII, IX, X.
2. Positional Number System
• Symbols represent different values depending upon the position.
• Example: Decimal numbers: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
Types of Positional Number System
• Binary number system
• Decimal number system
• Octal number system
• Hexadecimal number system
3
Number Systems
A bits is a digit in binary numbers.
• It is the basic unit of information in a computer.
• It is the smallest unit of measurement
• It is a state of on or off in a digital circuit.
• We use 1 or 0 to represent the state.
Bits can be grouped together for
larger range of numbers.
Example: 2 switches are used to represent 4 values:
(00), (01), (10) and (11).
4
Number Systems
A byte is a group of eight bits.
• It is the smallest possible addressable unit of computer storage.
• Used to represent one character.
A word is a contiguous group of bytes.
• Words can be any number of bits or bytes.
• Word sizes of 16, 32, or 64 bits are most common.
Use consecutive bytes to store large data bits
e.g. 4 bytes = 1 word
1 1 00 1 1 0 1 000 1 1 1 0 1 1 00 1 00 1 0
1 2 3 4...
bytes 5
Number Systems
Humans can’t work well with large binary numbers.
Memory addresses and other data can be quite large.
Bits can be grouped together to represent other types
of number systems.
Octal digit = 3 bits.
It use 3 bits to generate 8 symbols.
It is also known as base 8 .
Hexadecimal digit = 4 bits.
It use 4 bits to generate 16 symbols.
It is also known as base 16.
6
Number Systems
Any number can be written in base b, using b digits
If b = 10 we have decimal with 10 digits
If b = 2 we have binary with 2 digits
If b = 8 we have octal with 8 digits
If b = 16 we have hexadecimal with 16 digits
Name b
b=10
Note:
b=2
Base b is called radix r.
b=8
b=16
7
Number Systems
8
Number Systems
In binary terms:
• Most significant bit (MSB) is the left-most bit that has the
greatest effect on the number
• Least significant bit (LSB) is the right-most bit.
Approaches to store numbers
1. Fixed point notation: fixed number of digits after the point.
2. Floating point notation: a varying
number of digits after the point.
9
Conversion between Bases
In fixed point numbers, each number has two
parts: an integer part and a fractional part.
(a3a2 a1a0 .a1a2 ) r
a3 r 3 a2 r 2 a1 r1 a0 r 0 a
For converting, we start at the point (radix point).
The integer part is converted from right to left.
The fractional part is converted from left to right
10
Conversion from Base r to Decimal
Method
(a3a2 a1a0 .a1a 2 ) r
1 2
a3 b a2 r a1 r a0 r a1 r a 2 r
3 2 1 0
Binary System (base = 2)
(1011)2 = 1*23 + 0*22 + 1*21+ 1*20
= 1*8 + 0*4 + 1*2+ 1*1
= 8 + 0 + 2 + 1 = 11
(101.101)2 = 1x22 + 0x11 + 1x20 + 1x2-1 + 0x2-2 +
1x2-3
= 5.625
Ex: (11010.11)2 = (?)10 11
Conversion from Base r to Decimal
Octal number system (base = 8)
(4271)8 = 4*83 + 2*82 + 7*81 + 1*80
= 4*512 + 2*64 + 7*8 + 1*1
= 2048 + 128 + 56 + 1
= 2233
Hexadecimal number system (base = 16)
(4A1C)16 = 4*163 + A*162 + 1*161 + C*160
= 4*4096 + 10*256 + 1*16 + 12*1
= 16384 + 2560 + 16 + 12
= 18972
Ex: (4021.23)5 = (?)10
12
Exercises
Convert Hex (2AC5.D) to decimal, Octal and Binary
Convert Decimal (225.225)10 to Binary, Octal and Hex
13
Exercises
(10949.8125)10 (0010 1010 1100 0101.1101)2 (25305.64)8
(1110 0001.0011 1001 1001)2 (341.163---)8 (E1.399--)16
14
Conversion from Decimal to Base r
Method
Step 1:- If the number has radix point, then it is
necessary to separate the number into an integer
part and a fractional part.
Step 2:- For integer part, divide it and its all
successive quotients by r until new quotient
becomes zero, and accumulate the remainders in
the reverse order.
Step 3:- For fractional part, multiply it and its all
successive fractional parts by r until new
fractional part becomes zero, and accumulate the
integer parts in the order.
15
Conversion from Decimal to Binary
(41.6875)10 = (?)2
Integer Remainder Integer Fraction
41 0.6875x 2 = 1 + 0.375
20 1 0.375 x 2 = 0 + 0.75
10 0 0.75 x 2 = 1 + 0.5
5 0 0.5 x2= 1 +0
2 1
0.1011
1 0 101001 answer
0 1 answer
16
Conversion from Decimal to Octal
(234.513)10 = (?)8
Integer Remainder Integer Fraction
234 0.513 x 8 = 4 + 0.104
29 2 0.104 x 8 = 0 + 0.832
3 5 0.832 x 8 = 6 + 0.656
0 3 0.656 x 8 = 5 + 0.248
0.248 x 8 = 1 + 0.984
0.40651…..
352 answer
answer
17
Conversion from Decimal to Hexadecimal
(234.513)10 = (?)16
Integer Remainder Integer Fraction
234 0.513 x 16 = 8 + 0.208
14 A 0.208 x 16 = 3 + 0.328
0 E 0.328 x 16 = 5 + 0.248
0.248 x 16 = 3 + 0.968
0.968 x 16 = F + 0.488
0.8353F…..
EA
answer
answer
18
Conversion from Binary to Octal
Partition binary number into groups of 3 digits
starting from the radix point
When it’s not a multiple of 3, you can add 0s to the
left or right as you want depending on radix point
Replace each group of 3 binary digits by the
correspondent octal digit
Example
(11101010.1111)2 = (011 101 010 . 111 100)2
(11101010)2 = (352.74)8
19
Conversion from Binary to Hexadecimal
Partition binary number into groups of 4 digits
starting from the radix point
When it’s not a multiple of 4, you can add 0s to the
left or right as you want depending on radix point
Replace each group of 4 binary digits by the
correspondent hexadecimal digit
Example
(111101010.111001)2 = (0001 1110 1010 . 1110
0100)2
(111101010.111001)2 = (1EA.E4)16
20
Conversion from Octal to Binary
Replace each octal digit by the 3 corresponding
binary digits. You can suppress Leading 0s
Example
(352)8 = (011 101 010)2 = (11101010)2
For conversion from octal to hexadecimal, convert
first to binary, then from binary to hexadecimal
Example
(352)8 = (011 101 010)2 = (11101010)2
(11101010)2 = (1110 1010)2 = (EA)16
(352)8 = (EA)16 21
Conversion from Hexadecimal to Binary
Replace each hexadecimal digit by the 4
corresponding binary digits. You can suppress
Leading 0s
Example
(EA)16 = (1110 1010)2 = (11101010)2
For conversion from hexadecimal to octal, convert
first to binary, then from binary to octal
Example
(EA)16 = (1110 1010)2 = (11101010)2
(11101010)2 = (011 101 010)2 = (352)8
(EA)16 = (352)8 22
Unsigned and Signed Binary Numbers
Binary
Number
Unsigned Signed
Positive and Negative
Only Positive Numbers numbers
Sign- 1's 2's
Magnitude Complement Complement
Two 0’s Two 0’s Only one 0
23
Unsigned Binary Numbers
In unsigned numbers, all bits are used to represent
the number including the most significant bit (MSB).
Example: The binary numbers below are unsigned,
the equivalent decimals are:
00101001 = (41)10
10101001 = (169)10
24
Signed Binary Numbers
The sign bit is the most significant bit (MSB) represents
the sign of the number.
The sign bit is 0 for positive (+) and 1 for negative (-).
Signed numbers can be represented in different
representations:
Sign-Magnitude representation.
1’s - complement representation
2’s - complement representation
25
Signed Numbers
Signed-Magnitude Representation
This notation consists of a magnitude and a sign.
The leftmost bit (MSB) represents the sign bit and the rest
represents the number itself (magnitude).
To negate a number, just change its sign bit from 0 to 1.
It’s used in ordinary arithmetic.
Examples: assuming Signed-Magnitude
(+9)10 = (01001)2
(-9)10 = (11001)2
Exercise: assuming Signed-Magnitude
(1101)2 = ( -5 )10
(-19)10 = ( 10010011 )2 (Use 8 bits)
26
Signed Numbers
1’s-Compelement Representation
Positive numbers are represented as it is like signed positive number
(unsigned number).
Just like signed-magnitude, the (MSB) represents the sign bit.
To get the negation of a number, all bits are inverted including the sign
bit.
Example 1: use 1’s complement to find the negative of the number (+9)
(+9)10 = (01001)2
(-9)10 = (10110)2
Example 2: Assuming 1’s complement, what is the binary
representation of (-19)10 in 8-bits
(19)10 = (00010011) 2 , (-19)10 = (11101100) 2
Example 3: Assuming 1’s complement, what is the decimal number of
(11111101)2
It’s a negative number since (MSB) is 1
(11111101)2 = ( -2 )10 27
Signed Numbers
2’s-Compelement Representation
Positive numbers are represented as it is like signed positive number (unsigned
number).
Just like signed-magnitude, the (MSB) represents the sign bit.
To get the negation of a number, all bits are inverted including the sign bit;
then, add 1.
Example 1: use 2’s complement to find the negative of the number (+9)
(+9)10 = (01001)2
(-9)10 = (10110)2 + (1) 2 = (10111) 2
Example 2: Assuming 2’s complement, what is the binary
representation of (-19)10 in 8-bits
(19)10 = (00010011) 2 , (-19)10 = (11101100) 2 + (1) 2 = (11101101) 2
Example 3: Assuming 2’s complement, what is the decimal number of
(11111101)2
It’s a negative number since (MSB) is 1, take the 2’s complement, convert to decimal
and add (-) sign
(11111101)2 = ( -3 )10 28
Signed Binary Numbers
29
Binary Addition
Arithmetic operations with numbers in base r follow the same rules as
for decimal numbers
Given two binary digits (X, Y), a carry in (Z); we get following sum (S)
and carry (C):
Z 0 0 0 0
Carry in (Z) of 0: X 0 0 1 1
+Y +0 +1 +0 +1
CS 00 01 01 10
Z 1 1 1 1
X 0 0 1 1
Carry in (Z) of 1: +Y +0 +1 +0 +1
CS 01 10 10 11 30
Adding Unsigned Binary Numbers
Extending this to two multiple bit examples:
Carries 0 0
Augend 01100 10110
Addend +10001 +10111
Sum
Note: The 0 is the default Carry-In to the least
significant bit.
Carries 00000 01100
Augend 01100 10110
Addend +10001 +10111
Sum 11101 101101
31
Subtracting Unsigned Binary Numbers
using 2’s complement
The subtraction of two n-digit unsigned binary
numbers M-N using 2’s complement can be done as
follows:
1. Add the minuend, M, to the 2’s complement of the
subtrahend, N.
2.If M N, the end carry is discarded;
3.If M < N, there is no end carry. Then take the 2’s
complement of the result and place a negative
sign in front.
32
Subtracting Unsigned Binary Numbers
using 2’s complement
33
Adding Signed Binary Numbers
The addition of two signed binary numbers with
negative numbers represented in 2’s-complement
form is obtain from the addition of the two numbers,
including their sign bits. A carry out of the sign-bit
position is discarded.
Ex:
Adding two positive numbers (6)+(13) represented
in 8-bits
(6) 00000110
(13) 00001101
+19 00010011
34
Adding Signed Binary Numbers
Ex:
Adding two negative numbers (-6)+(-13)
represented in 8-bits
(-6) is represented in 2’s complement
(+6) = (00000110), (-6) = (11111010)
(-13) is represented in 2’s complement
(+13) = (00001101), (-13) = (11110011)
(-6) 11111010
Carry out
(-13) 11110011 discarded
(-19) 111101101
35
Adding Signed Binary Numbers
Ex:
Adding two negative numbers (-6)+(+13)
represented in 8-bits
(-6) is represented in 2’s complement
(+6) = (00000110), (-6) = (11111010)
(+13) = (00001101)
(-6) 11111010
Carry out
(+13) 00001101 discarded
(+7) 100000111
36
Adding Signed Binary Numbers
Ex:
Adding two negative numbers (+6)+(-13)
represented in 8-bits
(+6) = (00000110)
(-13) is represented in 2’s complement
(+13) = (00001101), (-13) = (11110011)
(+6) 00000110
(-13) 11110011
(-7) 11111001
37
Subtracting Signed Binary Numbers
Subtracting of two signed binary numbers when
negative numbers are in 2’s-complement is obtained
from taking the 2’s-complement of the subtrahend
(including the sign bit) and adding it to the minuend
(including the sign bit).
Similar to subtracting unsigned binary numbers using
2’s complement
The procedure adopts the following relationship
( A) ( B ) ( A) ( B )
( A) ( B ) ( A) ( B )
38
Subtracting Signed Binary Numbers
Ex: (+6) – (+13) = (+6) + (-13)
(+6) = (00000110), (+13) = (00001101),
2’s complement of (+13) = (-13) = (11110011)
(00000110) + (11110011) = (11111001) = (-7)
Ex: (-6) – (-13) = (-6) + (+13)
(+6) = (00000110, (-6) = (11111010)
(+13) = (00001101)
(11111010) + (00001101) = (00000111) = (+7)
( A) ( B ) ( A) ( B )
( A) ( B ) ( A) ( B )
39
Overflow
If we start with two n-bit numbers and the sum occupies n
+ 1 bits, we say that an overflow occurs.
Unsigned numbers
perform (9) + (8) in 4-bits
(1001) + (1000) = (10001), ends up with 5-bit, therefore, an overflow
occurs.
The final result is (0001) in 4-bits which is less than the correct result
Signed numbers (2’s complement)
It occurs when two numbers with the same sign are added and the result
has different sign.
Perform (-5) + (-6) in 4-bits
(5) = (0101), (-5)=(1011), (6)=(0110), (-6)=(1010)
(1011) + (1010) = (10101) discard the last bit then the final result (0101)
The result is positive while the two numbers are negative, then, an overflow
occurs.
40
Floating Point Representation
IEEE Standard 754 Floating Point Numbers
Three components
Sign
Exponent
Significant (Mantissa)
Single Precision (32 bits)
Sign (1 bit), Exponent (8 bits), Significant (23 bits)
Double Precision (64 bits)
Sign (1 bit), Exponent (11 bits), Significant (52 bits)
41
Floating Point Representation
Single Precision
31 30 23 22 0
S Exponent Significant (Mantissa)
Number = (-1)s * 1.Significant * 2 (Exponent -127)
Double Precision
63 62 52 51 0
S Exponent Significant (Mantissa)
Number = (-1)s * 1.Significant * 2 (Exponent -1023)
42
Floating Point Representation
32 bit floating-point representation:
1. Convert a number to: S * 1.fraction * 2(Exp)
The first bit (the left of the binary point) is always 1.
2. Compute the three components:
Sign= 0 or 1
0: for positive number. 1: for negative number.
Exponent= (Exp+ 127 )2
Example: if Exp=7, Exponent=(7 + 127)2=(134)2= 10000110
Example: if Exp=−4, Exponent=(−4 + 127)2=(123)2= 01111011
Fraction= fraction+the rest is 0s
43
Floating Point Representation
64 bit floating-point representation:
1. Convert a number to: S * 1.fraction * 2(Exp)
The first bit (the left of the binary point) is always 1.
2. Compute the three components:
Sign= 0 or 1
0: for positive number. 1: for negative number.
Exponent= (Exp+ 1023 )
Example: if Exp=7, Exponent=(7 + 1023)=(1030)= 10000000110
Example: if Exp=−4, Exponent=(−4 + 1023)=(1019)= 01111111011
Fraction= fraction+the rest is 0s
44
Floating Point Representation
Example1: Present +11100100 in 32 bit floating point.
Answer:
1. +11100100 = + 1.11001 × 27
2. Compute the three components:
Sign = 0 (positive number)
Exponent = (7 + 127)2=(134 )2 = (1000 0110)2
Fraction = 11001+the rest is 0s
So the presentation is:
0 1000 0110 110 0100 0000 0000 0000 0000
45
Floating Point Representation
Example2: Present -110110011.01 in 32 bit floating
point.
Answer:
1. -110110011.01 = -1.1011001101 * 28
2. Compute the three components:
Sign = 1 (negative number)
Exponent = (8 + 127)2= (135)2 =(1000 0111)2
Fraction = 1011001101+the rest is 0s
So the presentation is:
1 1000 0111 101 1001 1010 0000 0000 0000
46
Floating Point Representation
Example3: Present 101.111001 in 32 bit floating point.
Answer:
1. 101.111001 = +1.01111001 * 22
2. Compute the three components:
Sign = 0 (positive number)
Exponent = (2 + 127)2= (129)2 =(1000 0001)2
Fraction = 01111001 +the rest is 0s
So the presentation is:
0 1000 0001 011 1100 1000 0000 0000 0000
47
