Chapter 6 -- integer arithmetic
all about integer arithmetic.
-------------------------------------
operations we'll get to know (and love):
addition
subtraction
multiplication
division
logical operations (not, and, or, nand, nor, xor, xnor)
shifting
the rules for doing the arithmetic operations vary depending
on what representation is implied.
A LITTLE BIT ON ADDING
----------------------
an overview.
carry in a b | sum carry out
---------------+----------------
0 0 0 | 0 0
0 0 1 | 1 0
0 1 0 | 1 0
0 1 1 | 0 1
1 0 0 | 1 0
1 0 1 | 0 1
1 1 0 | 0 1
1 1 1 | 1 1
|
a 0011
+b +0001
-- -----
sum 0100
its really just like we do for decimal!
0 + 0 = 0
1 + 0 = 1
1 + 1 = 2 which is 10 in binary, sum is 0 and carry the 1.
1 + 1 + 1 = 3 sum is 1, and carry a 1.
ADDITION
--------
unsigned:
just like the simple addition given.
examples:
100001 00001010 (10)
+011101 +00001110 (14)
------- ---------
111110 00011000 (24)
ignore (throw away) carry out of the msb.
Why? Because computers ALWAYS work with a fixed precision.
sign magnitude:
rules:
- add magnitudes only (do not carry into the sign bit)
- throw away any carry out of the msb of the magnitude
(Due, again, to the fixed precision constraints.)
- add only integers of like sign ( + to + or - to -)
- sign of result is same as sign of the addends
examples:
0 0101 (5) 1 1010 (-10)
+ 0 0011 (3) + 1 0011 (-3)
--------- ---------
0 1000 (8) 1 1101 (-13)
0 01011 (11)
+ 1 01110 (-14)
----------------
don't add! must do subtraction!
one's complement:
by example
00111 (7) 111110 (-1) 11110 (-1)
+ 00101 (5) + 000010 (2) + 11100 (-3)
----------- ------------ ------------
01100 (12) 1 000000 (0) wrong! 1 11010 (-5) wrong!
+ 1 + 1
---------- ----------
000001 (1) right! 11011 (-4) right!
so it seems that if there is a carry out (of 1) from the msb, then
the result will be off by 1, so add 1 again to get the correct
result. (Implementation in HW called an "end around carrry.")
two's complement:
rules:
- just add all the bits
- throw away any carry out of the msb
- (same as for unsigned!)
examples
00011 (3) 101000 111111 (-1)
+ 11100 (-4) + 010000 + 001000 (8)
------------ -------- --------
11111 (-1) 111000 1 000111 (7)
after seeing examples for all these representations, you may see
why 2's complement addition requires simpler hardware than
sign mag. or one's complement addition.
SUBTRACTION
-----------
general rules:
1 - 1 = 0
0 - 0 = 0
1 - 0 = 1
10 - 1 = 1
0 - 1 = borrow!
unsigned:
- it only makes sense to subtract a smaller number from a larger one
examples
1011 (11) must borrow
- 0111 (7)
------------
0100 (4)
sign magnitude:
- if the signs are the same, then do subtraction
- if signs are different, then change the problem to addition
- compare magnitudes, then subtract smaller from larger
- if the order is switched, then switch the sign too.
- when the integers are of the opposite sign, then do
a - b becomes a + (-b)
a + b becomes a - (-b)
examples
0 00111 (7) 1 11000 (-24)
- 0 11000 (24) - 1 00010 (-2)
-------------- --------------
1 10110 (-22)
do 0 11000 (24)
- 0 00111 (7)
--------------
1 10001 (-17)
(switch sign since the order of the subtraction was reversed)
one's complement:
figure it out on your own
two's complement:
- change the problem to addition!
a - b becomes a + (-b)
- so, get the additive inverse of b, and do addition.
examples
10110 (-10)
- 00011 (3) --> 00011
------------ |
\|/
11100
+ 1
-------
11101 (-3)
so do
10110 (-10)
+ 11101 (-3)
------------
1 10011 (-13)
(throw away carry out)
OVERFLOW DETECTION IN ADDITION
unsigned -- when there is a carry out of the msb
1000 (8)
+1001 (9)
-----
1 0001 (1)
sign magnitude -- when there is a carry out of the msb of the magnitude
1 1000 (-8)
+ 1 1001 (-9)
-----
1 0001 (-1) (carry out of msb of magnitude)
2's complement -- when the signs of the addends are the same, and the
sign of the result is different
0011 (3)
+ 0110 (6)
----------
1001 (-7) (note that a correct answer would be 9, but
9 cannot be represented in 4 bit 2's complement)
a detail -- you will never get overflow when adding 2 numbers of
opposite signs
OVERFLOW DETECTION IN SUBTRACTION
unsigned -- never
sign magnitude -- never happen when doing subtraction
2's complement -- we never do subtraction, so use the addition rule
on the addition operation done.
MULTIPLICATION of integers
0 x 0 = 0
0 x 1 = 0
1 x 0 = 0
1 x 1 = 1
-- longhand, it looks just like decimal
-- the result can require 2x as many bits as the larger multiplicand
-- in 2's complement, to always get the right answer without
thinking about the problem, sign extend both multiplicands to
2x as many bits (as the larger). Then take the correct number
of result bits from the least significant portion of the result.
2's complement example:
1111 1111 -1
x 1111 1001 x -7
---------------- ------
11111111 7
00000000
00000000
11111111
11111111
11111111
11111111
+ 11111111
----------------
1 00000000111
-------- (correct answer underlined)
0011 (3) 0000 0011 (3)
x 1011 (-5) x 1111 1011 (-5)
------ -----------
0011 00000011
0011 00000011
0000 00000000
+ 0011 00000011
--------- 00000011
0100001 00000011
not -15 in any 00000011
representation! + 00000011
------------------
1011110001
take the least significant 8 bits 11110001 = -15
DIVISION of integers
unsigned only!
example of 15 / 3 1111 / 011
To do this longhand, use the same algorithm as for decimal integers.
LOGICAL OPERATIONS
done bitwise
X = 0011
Y = 1010
X AND Y is 0010
X OR Y is 1011
X NOR Y is 0100
X XOR Y is 1001
etc.
SHIFT OPERATIONS
a way of moving bits around within a word
3 types: logical, arithmetic and rotate
(each type can go either left or right)
logical left - move bits to the left, same order
- throw away the bit that pops off the msb
- introduce a 0 into the lsb
00110101
01101010 (logically left shifted by 1 bit)
logical right - move bits to the right, same order
- throw away the bit that pops off the lsb
- introduce a 0 into the msb
00110101
00011010 (logically right shifted by 1 bit)
arithmetic left - move bits to the left, same order
- throw away the bit that pops off the msb
- introduce a 0 into the lsb
- SAME AS LOGICAL LEFT SHIFT!
arithmetic right - move bits to the right, same order
- throw away the bit that pops off the lsb
- reproduce the original msb into the new msb
- another way of thinking about it: shift the
bits, and then do sign extension
00110101 -> 00011010 (arithmetically right shifted by 1 bit)
1100 -> 1110 (arithmetically right shifted by 1 bit)
rotate left - move bits to the left, same order
- put the bit that pops off the msb into the lsb,
so no bits are thrown away or lost.
00110101 -> 01101010 (rotated left by 1 place)
1100 -> 1001 (rotated left by 1 place)
rotate right - move bits to the right, same order
- put the bit that pops off the lsb into the msb,
so no bits are thrown away or lost.
00110101 -> 10011010 (rotated right by 1 place)
1100 -> 0110 (rotated right by 1 place)
SASM INSTRUCTIONS FOR LOGICAL AND SHIFT OPERATIONS
SASM has instructions that do bitwise logical operations and
shifting operations.
lnot x x <- NOT (x)
land x, y x <- (x) AND (y)
lor x, y x <- (x) OR (y)
lxor x, y x <- (x) XOR (y)
llsh x x <- (x), logically left shifted by 1 bit
rlsh x x <- (x), logically right shifted by 1 bit
rash x x <- (x), arithmetically right shifted by 1 bit
rror x x <- (x), rotated right by 1 bit