Transcript Step 1

DIGITAL SYSTEMS TCE1111
Representation and Arithmetic
Operations with Signed Numbers
Week 6 and 7
(Lecture 1 of 2)
DIGITAL SYSTEMS TCE1111
What we are going to discuss?
• How to find 1’s and 2’s complement of a given binary
number?
• How to represent negative integers using three ways –
sign-magnitude,1’s complement and 2’s complement
representation
• Arithmetic operations with 2’s complement numbers –
Addition, Subtraction, Multiplication, Division
• Overflow Problem and Detection in the addition of
signed numbers in 2’ s complement representation.
2
DIGITAL SYSTEMS TCE1111
Finding 1’s complement
Change all the 1s to 0s and all the 0s to 1s
Binary number
0001100100101
1’s complement 1110011011010
3
DIGITAL SYSTEMS TCE1111
Example of inverters used to obtain the 1’s
complement of a binary number.
4
DIGITAL SYSTEMS TCE1111
Finding 2’s complement
2’s complement = 1’s complement +1
Binary number
111000101010001
1’s complement 000111010101110
Add
1
2’s complement 000111010101111
5
DIGITAL SYSTEMS TCE1111
Example of obtaining the 2’s complement of a
negative binary number.
6
DIGITAL SYSTEMS TCE1111
Representation of Signed Integers in Binary –
Three forms
Sign bit – a 0 is for positive a 1 is for negative
Sign-Magnitude form – a negative number has the same magnitude as the
corresponding positive number but the sign bit is a 1 rather than a zero
Example:
+43 in 8-bit S-M form = 0 0101011
-43 in 8-bit S-M form = 1 0101011
1’s complement form- a negative number is the 1’s complement of the
corresponding positive number
Example: +43 in 8-bit 1’s complement form = 00101011
-43 in 8-bit 1’s complement form = 11010100
2’s complement form- a negative number is the 2’s complement of the
corresponding positive number
Example: +43 in 8-bit 2’s complement form = 00101011
-43 in 8-bit 2’s complement form = 11010101
7
DIGITAL SYSTEMS TCE1111
Determination of decimal value of signed
numbers (1)…
Sign-magnitude form – convert all but the MSB to decimal
and call the decimal value negative if the MSB is 1
Example: 0 1010011 = 64+16+2+1 = +83 since MSB is 0
1 1010011 = 64+16+2+1 = -83 since MSB is 1
1’s complement form – if the bit sign is 0 sum the weighted
values of the the binary number, if the bit sign is 1 the sum
the weighted value of the binary number assigning the MSB
a negative weight and add 1
Example: 01010011 = 64+16+2+1 = + 83 since MSB is 0
10101100 = -128+32+8+4= - 84 +1 since MSB is 1
= - 83
8
DIGITAL SYSTEMS TCE1111
Determination of decimal value of signed
numbers (2)
2’s complement form - if the bit sign is 0 sum the weighted values
of the binary number, if the bit sign is 1 the sum the weighted
value of the binary number assigning the MSB a negative weight
• Example:
01010011 = 64+16+2+1 = + 83 since MSB is 0
10101101 = -128+32+8+4+1= - 83 since MSB is 1
9
DIGITAL SYSTEMS TCE1111
Table of 8 bit
Two’s Complement numbers
127 01111111
-1
11111111
……….
-2
11111110
5 00000101
-3
11111101
4 00000100
-4
11111010
3 00000011
-5
11111011
2 00000010
………
1 00000001
-128
10000000
0 00000000
10
DIGITAL SYSTEMS TCE1111
Range of 2’s complement representation
• Range of values for n-bit numbers for 2’s complement signed
number representation
- (2n-1) to +(2n-1 – 1)
Example:
• For 4 bit 2’s complement representation, range = -8 to +7
• For 8 bit 2’s complement representation, range = -128 to +127
• For 16 bit 2’s complement representation, range = -32,768 to
+32,767
11
DIGITAL SYSTEMS TCE1111
Arithmetic operations with 2’s complement
numbers – Addition
• Add the two numbers and discard any final carry bit.
• Example:
Add (34) + (-46) in 8-bit 2’s complement arithmetic
34 = 00100010
-46 = 11010010
--------------12= 11110100
----------------
12
DIGITAL SYSTEMS TCE1111
Overflow problem and detection (1)…
• Problem: When two numbers are added and the
number of bits required to represent the sum
exceeds the number of bits in the two numbers,
an overflow occurs.
• When it can occur? Overflow may occur only
when both numbers are positive or both numbers
are negative.
13
DIGITAL SYSTEMS TCE1111
Overflow problem and detection (2)
• Detection of Overflow:
– When two operands are having the same sign and the result is
having different sign, then there is overflow
– If carry into the sign bit is different from carry out of the sign
bit, then there is overflow
– Example: 01101110
01011011
------------11001001
-------------Operands sign = +ve (0) Result sign = -ve (1), hence overflow
occurs.
(or) carry into the sign bit = 1, carry out of sign bit =0, hence
overflow occurs.
14
DIGITAL SYSTEMS TCE1111
Arithmetic operations with 2’s complement numbers –
Subtraction-Example (27-12)
Example : (27-12) = 27 + -12
27
00011011
Subtraction is addition
Two’s Comp 00011011
with the sign of the
subtrahend changed
12
00001100
Comp
11110011
Add 1
1
Two’s comp
11110100
-12
ADD 00011011
11110100
Carry Disregarded
1 00001111
15
15
DIGITAL SYSTEMS TCE1111
Multiplication
•
•
Two methods: Direct addition and Partial products
The sign of the product of a multiplication depends on the signs
of the multiplicand and the multiplier according to the following
two rules:
1. If the signs are the same, the product is positive
2. If the signs are different, the product is negative
16
DIGITAL SYSTEMS TCE1111
Multiplication
• Direct addition method - add the multiplicand a number of times equals to the
multiplier. Disadvantage is this approach becomes very lengthy if the
multiplier is a large number.
• Example:
17
DIGITAL SYSTEMS TCE1111
Multiplication
Partial Product method
• Procedure:
– Step 1: Determine if the signs of the multiplicand and multiplier are the
same or different to determine the sign of the product.
(If the signs are the same, the product is positive. If the signs are different,
the product is negative)
- Step 2: Change any negative number to true (uncomplemented) form by
finding 2’s complement
- Step 3: Starting with least significant multiplier bit, generate the partial
products. When the multiplier bit is 1, the partial product is the same as the
multiplicand. When the multiplier bit is 0, the partial product is zero. Shift
each successive partial product one bit to the left.
- Step 4: Add each successive partial product to the sum of the previous
partial products to get the final product.
- Step 5: If the sign bit that was determined in step 1 is negative, take the 2’s
complement of the product. If positive, leave the product in true form.
Attach the sign bit to the product.
18
DIGITAL SYSTEMS TCE1111
Multiplication – example
19
DIGITAL SYSTEMS TCE1111
Division
The numbers in a division are the dividend, the divisor and the
quotient.
dividend
 quotient
divisor
The division operation in computers is accomplished using subtraction. Example:
21
- 7
14
- 7
7
- 7
0
The sign of the quotient depends on the signs of the dividend and the divisor according to
the two rules:
1. If the signs are the same, the quotient is positive
2. If the signs are different, the quotient is negative
20
DIGITAL SYSTEMS TCE1111
Division
When tow binary numbers are dividend, both numbers must be
in true ( uncomplemented) form. The basic steps in division
process are as follows:
– Step 1: Determine if the signs of the dividend and divisor are the same or
different. This determines the sign of the quotient. (If the signs are the
same, the quotient is positive. If the signs are different, the quotient is
negative). Initialize the quotient to zero.
– Step 2: Subtract the divisor from the dividend using 2’s complement
addition to get the first partial remainder and add 1 to the quotient. If this
partial remainder is positive, go to step 3. If the partial remainder is zero or
negative, the division is complete.
– Step 3: Subtract the divisor from the partial remainder and add 1 to the
quotient. If the result is positive, repeat for next partial remainder. If the
result is zero or negative, the division is complete.
– Step 4: Continue to subtract the divisor from the dividend and the partial
remainders until there is a zero or negative result. Quotient is the number
of times that the divisor is subtracted.
21
DIGITAL SYSTEMS TCE1111
Division (1)…
• Example: Divide 01100100 by 00011001
Solution:
Step 1: The signs of both numbers are positive, so the quotient will be positive.
The quotient is initially zero: 00000000
Step 2: Subtract the divisor from the dividend using 2’s complement addition by
discarding carry if any.
01100100
Dividend
+ 11100111
2’s complement of divisor
------------------01001011
Positive 1st partial remainder
-------------------Add 1 to the Quotient: 00000000 + 00000001 = 00000001
22
DIGITAL SYSTEMS TCE1111
Division (3)…
• Step 3: Subtract the divisor from the 1st partial remainder using 2’s
complement addition
01001011
1st partial remainder
+
11100111
2’s complement of divisor
------------00110010
Positive 2nd partial remainder
-------------Add 1 to the quotient: 00000001 + 00000001 = 00000010.
Step 4: Subtract the divisor from the 2nd partial remainder using 2’s complement
addition.
00110010
2nd partial remainder
+
11100111
2’s complement of divisor
--------------00011001
Positive 3rd partial remainder
Add 1 to the quotient: 00000010 + 00000001 = 00000011.
23
DIGITAL SYSTEMS TCE1111
Division (4)
• Step 5: Subtract the divisor from the 3rd partial remainder using 2’s
complement addition.
00011001 3rd partial remainder
+
11100111 2’s complement of divisor
------------00000000
Zero remainder
-------------Add 1 to the quotient: 00000011 + 00000001 = 00000100 (final quotient). The
process is complete.
24