Transcript 05_IntegerAddition

Integer Operations
Computer Organization and Assembly Language: Module 5
Integer Operations
 Addition
 Unsigned
 2’s
complement, 1’s complement
 Subtraction
 Multiplication
 Division
Unsigned Integer Addition
 The
algorithm for addition of unsigned integers in a
positional representation works for any radix.

You learned this algorithm as a child
 Given
a pair of bit (digit) sequences X and Y, where
X = xnxn-1...x1x0
Y = ynyn-1...y1y0
i from 0 to n, add ci, xi and yi. If the sum is less than
the radix assign the sum to si and 0 to ci+1. Otherwise
subtract the radix from the sum and assign the result to si
and 1 to ci+1. ci is the carry bit in the ith bit position.
 For

Assume c0 = 0.
Unsigned Binary Addition
c1=1
c0 = 0
+
011 (310)
001 (110)
100 (410)
Note:
ci+1 =(xi+yi+ci)div 2
si =(xi+yi+ci)mod 2
1+1=10
s0
Unsigned Binary Addition
+
010010
011000
101010
+
000111
011001
100000
Overflow in Unsigned Addition
 In
a computer, the result of addition is stored in a
fixed sized container: a register.
 MIPS
registers contain 32 bits
 Sometimes
the result of addition is a number too
large to be represented: this is called overflow.
 In
unsigned addition, an overflow is indicated by a
value of 1 in the most significant carry bit (often
called the carry-out bit).
Overflow Example
 Assume
4-bit registers
Carry out of 1 from
11110
the most significant
position
1111
+
0001
10000
Although the true
result is 10000,
the register
contains 0000.
Biased Addition
 The
various biased representations use the same
addition algorithm as unsigned integers, with one
modification
 The
bias must be subtracted from the result
Complement Addition
 The
2’s complement representation uses the same
addition algorithm as unsigned integers.
 The
overflow condition is different
 Overflow occurs if xn-1 and yn-1 both have the same
value and sn-1 has a different value.
 This
is logically equivalent to cn-1 = cn-2
 Carry-out is otherwise ignored
 The
1’s complement representation adds a slight
wrinkle to the addition algorithm.
 If
the carry-out is 1, the sum is incremented by 1.
 Overflow is handled as it is for 2’s complement
2’s Complement Addition
+
0101 (5)
0010 (2)
0111 (7)
0101 (5)
+ 1101 (-3)
10010 (2)
Carry out
is discarded,
no overflow.
0011 (3)
+ 1100 (-4)
1111 (-1)
1001 (-7)
+ 0111 (7)
10000 (0)
2’s Complement Addition
1111 1000 (-8)
1111 1000 (-8)
1 1111 0000 (-16)
0111 1110 (126)
0110 0000 (96)
1101 1110 (-34)
0000 0101 (5)
0100 0000 (64)
0100 0101 (69)
1000 0010 (-126)
1111 1101 (-3)
1 0111 1111 (127)
overflow
1’s Complement Addition
0011 (+3)
+ 1100 (-3)
1111 (0)
1101 (-2)
+ 1011 (-4)
11000
carry-out is
added to the
+ 1
partial sum
1001 (-6)
0001 (+1)
+ 1001 (-6)
1010 (-5)
0111 (+7)
+ 1100 (-3)
10011
+ 1
0100 (+4)
Integer Subtraction
 The
complement representations can handle subtraction as
addition by first complementing the subtrahend, then
adding.

There is no subtraction algorithm for complement representations.
 All
other integer representations require separate logic to
handle subtraction.
For this reason, and because it has a unique zero, 2’s complement
is used to represent integers in almost all architectures.
 In such architectures, other representations are translated into 2’s
complement before addition/subtraction, then the result is
translated back into the original representation.

Integer Multiplication
Integer Multiplication
 It
may take as many as 2n bits to represent the
product of two n-bit numbers.
 Multiplication of unsigned binary integers can be
done with the same algorithm we use for decimal
multiplication.
 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 integers.
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 hi}
count = count + 1
rotate the multiplier right 1 bit
shift hi and lo one bit to the right
}
Unsigned Integer Multiplication
Multiplicand 1101
0110
Multiplier
Hi 0000
0000
Lo
Carry 0
Using 4-bit registers, multiply 13 by 6.
Unsigned Integer Multiplication
Multiplicand 1101
0011
Multiplier
Hi 0000
0000
Lo
Carry 0
After the first shift the lo bit of the multiplier is 1,
so we will add the multiplicand to hi.
Unsigned Integer Multiplication
Multiplicand 1101
0011
Multiplier
Hi 1101
0000
Lo
Carry 0
Unsigned Integer Multiplication
Multiplicand 1101
1001
Multiplier
Hi 0110
1000
Lo
Carry 0
After the shift the low bit of the multiplier is still 1.
We add the multiplicand to hi…
Unsigned Integer Multiplication
Multiplicand 1101
1001
Multiplier
Hi 0011
1000
Lo
Carry 1
…and the result is bigger than 4 bits. So carry is set
to one. The carry bit is shifted into hi…
Unsigned Integer Multiplication
Multiplicand 1101
1100
Multiplier
Hi 1001
1100
Lo
Carry 0
…and the low bit of hi is shifted into lo. One more
shift step will produce the answer.
Unsigned Integer Multiplication
Multiplicand 1101
0110
Multiplier
Hi 0100
1110
Lo
Carry 0
The multiplier is again 0110. The result, 1001110 is
78. And 6 x 13 = 78.
2’s Complement Multiplication
n-bit two’s complement integers, both
the multiplier and the multiplicand are sign
extended to 2n.
 This produces a 4n-bit result.
 The correct product is contained in the least
significant 2n bits of the 4n-bit result.
 With
2’s complement Multiplication
Multiplicand 1101
0110
Multiplier
Hi 0100
1110
Lo
Carry 0
Interpreted as 2’s complement numbers, this result
is –3 x 6 = 78, which is obviously false.
2’s complement Multiplication
Multiplicand
11111101
00000110
Multiplier
Hi
00000000
00000000
Lo
Carry
0
For an accurate result we must sign extend the
multiplier and multiplicand to 8 bits.
2’s complement Multiplication
Multiplicand
11111101
00000110
Multiplier
Hi
00000101
11101110
Lo
Carry
0
After multiplication, lo contains all the meaningful
data: 11101110 = - 18, which is –3 x 6!
Division
 Division
of unsigned binary integers is the
performed similar to the longhand division of
decimal numbers
 No convenient algorithm exists for division of
signed magnitude and complement integers
 Determine
sign of the result
 Take absolute value of the numbers
 Do unsigned division
 Convert the result to the original format
Division Algorithm
remainder = dividend
while count < no. of integer bits + 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
}