Chapter 6 -- integer arithmetic

all about integer arithmetic.
-------------------------------------

operations we'll get to know (and love):
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.

--------

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