Transcript Arithmetic & Logic Part 2

Arithmetic and
Logical Operations Part II
1
Unsigned Numbers
Addition in unsigned numbers is the
same regardless of the base.
 Given a pair of bit sequences X and Y,
where
X = xnxn-1...x1x0

Y = ynyn-1...y1y0
we need to add three terms: xi, yi, and ci
for each bit position i = 0...n.
 ci is the carry bit in the ith bit position.
Assume c0 = 0.
Example 15.1
+)
c1=1
011 (310)
001 (110)
100 (410)
Note:
ci+1 =(xi+yi+ci)div 2
zi =(xi+yi+ci)mod 2
1+1=10
z0
Example 15.2
+)
010010
011000
101010
000111
011001
100000
Overflow in Unsigned Numbers
Given a pair of n bit sequences X and Y,
we apply the following check for
overflow:
Overflow occurs if
(X + Y) mod 2  X + Y
 An overflow occurs if a sum is no longer
representable within a fixed number of
bits. An incorrect sum is produced when
there is a carry out from the most
significant position.

Example 15.3
Let the number of bits, n, be 4
1111
Carry out of 1 from
the most significant
0001
position
10000
also we can check using
(X + Y) mod 2n  X + Y
which gives us 0000  10000,
thus overflow occurs.
Sign Magnitude Integers
If two integers in sign magnitude have
the same sign, the two integers are
added.
 The sign of the result is the same as
that of the addends.
 The sign bit is not included in the
process.
 Any carry out from the most significant
bit of the magnitude is thrown away.

Example 15.4
1 00100 (-4)
+) 1 00101 (-5)
1 01001 (-9)
0 11111 (31)
0
1 (1)
0100000 (overflow)
0 00010 (2)
0 00111 (7)
0 01001 (9)
A carry out
from the most
significant bit
has occurred
If two integers have different signs, a
subtraction is performed and the sign of
the result is decided in advance. The
sign will be that of the integer with the
larger magnitude.
 The subtraction of unsigned or sign
magnitude integers is the same as the
longhand subtraction of decimal
numbers.
 For unsigned numbers, there are results
which are not representable.

Example 15.5
+)
+)
0 00101 (5)
1 00011 (-3)
0 00010 (2)
0 00100 (4)
1 00010 (-2)
0 00010 (2)
+)
1 00010 (-2)
0 00101 (5)
0 00011 (3)
becomes 0
is now 10
borrow
Overflow in Signed Magnitude
If both addends are of the same sign, and
there is a carry out from the most
significant bit of the magnitude then
overflow has occurred.
 If the addends have different signs,
overflow will not occur.

Two’s Complement
In two’s complement, the same
algorithm is applied to the operands
regardless of the sign.
 Adding two numbers is done by simply
applying the same algorithm used for
unsigned numbers.
 Subtraction can be performed simply by
adding the additive inverse of the
subtrahend.

Overflow in Two’s complement
In two’s complement, overflow does not
necessarily happen when there is a
carry out of the most significant bit.
 An overflow occurs when both addends
are of the same sign and the result is of
the opposite sign
 If the carry into the most significant bit is
not the same as the carry out from the
most significant bit an overflow has
occurred.

Example 15.6
0101 (5)
+ 0010 (2)
0111 (7)
0011 (3)
+ 1100 (-4)
1111 (-1)
0101 (5)
+ 1101 (-3)
10010 (2)
1001 (-7)
+ 0111 (7)
10000 (0)
carry out
discarded.
no overflow
Example 15.7
1111 1000 (-8)
1111 1000 (-8)
1111 0000 (-16)
0000 0101 (5)
0100 0000 (64)
0100 0101 (69)
0111 1110 (126)
0110 0000 (96)
1101 1110 (-34)
1000 0010 (-126)
1111 1101 (-3)
0111 1111 (127)
overflow
Observations
In Example 12.7, an overflow occurs when
the numbers have the same signs but the
result has a different sign.
 If you take both the carry-in of the msb
and carry-out from the msb as inputs to an
XOR boolean expression, the following
holds:

 if
the result is 1 there is an overflow
 if the result is 0 there is no overflow
One’s Complement

In one’s complement, addition is
performed similar to the two’s complement
with a slight modification:
The carry out from the most significant
bit is added to the partial sum.
Example 15.8
0011 (+3)
1100 (-3)
1111 (0)
1101 (-2)
1011 (-4)
carry-out is
11000
added to the
1
partial sum
1001 (-6)
0001 (+1)
1001 (-6)
1010 (+5)
0111 (+7)
1100 (-3)
10011
1
0100 (+4)
Multiplication
It may take as many as 2n bits to
represent the product of two n-bit
numbers
 Multiplication in unsigned numbers uses
the longhand method we are already
familiar with.
 By sign extending both the multiplier
and the multiplicand to the size needed
for the result, the algorithm for
multiplying 2’s complement is the same
as that of unsigned numbers

Multiplication Algorithm
while (count < no. of integer bits){
check if the multiplier’s last bit is 1
if (multiplier bit = 1){
add the multiplicand to the product}
shift the multiplicand left 1 bit
count = count + 1
shift the multiplier right 1 bit
}
Example 15.9
x
0010
0011
multiplicand
multiplier
0000
+
0000
+
0000
initial product
0000
0010
0010
0100
0110
multiplicand
shifted left
final product

If we have n-bit two’s complement
integers, we both sign extend the
multiplier and the multiplicand to the
size needed for the result, i.e., 2n.

By making both the multiplier and the
multiplicand 2n the result of the
operation will have 4n bits.

The correct product is contained in the
least 2n bits of the 4n-bit wide result
Example 15.10
Let the number of bits for integers be 4
bits, i.e. n = 4. We sign extend the
numbers using 2n bits.
-3 x 6 = ?
-3 = 1101
6 = 0110
11111101
00000110
showed only
relevant addends.
1111101
note: there are only two
111101
1’s in the multiplier
xxxxxxxx11101110
-18
discard
Example 15.11
2 x -2 = -4
0000 0010
x 1111 1110
2 = 0010
0000
0000
0000
0001
+)
0010
0100
1000
0000
1111
-2 = 1110
0000
0100
Note: each addend
1000 is the multiplicand
shifted left 1 bit
0000
in each step
0000
0000
0000
0000
1100 (-4)
Example 15.12
-1 x -2 = ?
-1 = 1111
11111111 (-1)
11111110 (-2)
11111110
11111100
11111000
11110000
11100000
11000000
10000000
00000010 (+2)
-2 = 1110
Division
Division of unsigned binary numbers is the
performed similar to the longhand division
of decimal numbers
 No convenient algorithm exists for division
of signed magnitude and complement
integers
 An exception that must be handled is
division by zero

Division Algorithm
Align Most Significant Bits
remainder = dividend
while count < # bits shifted + 1{
remainder = remainder - divisor
if (remainder < 0){
remainder = remainder + divisor
shift left quotient & set lsb to 0}
else
shift left quotient & set lsb to 1
shift the divisor right
count = count + 1
}
Example 15.13
What is 31/4? (00011111 / 0100)
C
0
1
2
Q
0001
0011
0111
D
0001 0000
0000 1000
0000 0100
R
0001 1111
0000 1111
0000 0111
R-D
1111
0111
0011
Notice the alignment of the bits for the D. 0100 became
00010000. The D was shifted left twice to be aligned.
Count is 2+1=3, so the loop ends here.
Example 12.14
What is the result of 99/3? (01100011 / 0011)
C
0
1
2
3
4
5
Q
0000 0001
0000 0010
0000 0100
0000 1000
0001 0000
0010 0001
D
0110 0000
0011 0000
0001 1000
0000 1100
0000 0110
0000 0011
R
0110 0011
0000 0011
0000 0011
0000 0011
0000 0011
0000 0011
R-D
0011
Neg
Neg
Neg
Neg
0
Notice we get the right answer just as the loop ends from the count.
Dividing Signed Numbers
We can use the algorithm to perform
division on the absolute values of the
numbers.
 Compare the signs of the dividend and
the divisor. If they are the same, the
quotient is positive. If they are not the
same, the quotient is negative.
 The sign of the remainder is always the
same as the sign of the dividend
