COMPUTER ARITHMETIC: INTEGER ARITHMETIC

NEGATION

The negation of an integer can be formed with the following rules:

1. Set each 1 to 0 and each 0 to 1.
2. Add 1.

Special case:

1. Negation of 0 is 0.
2. Negation of an n-bit word of 2^n, will get back the same number.

ADDITION AND SUBTRACTION

To Subtract a number (subtrahend) from another (minuend), take the negation of the subtrahend and add it to the minuend.

Block Diagram of Hardware for Addition and Subtraction

MULTIPLICATION

UNSIGNED INTEGER

Multiplication of Unsigned Binary Integers

Hardware Implementation of Unsigned Binary Multiplication

1. Multiplier and multiplicand are loaded into tow registers (Q and M).
2. A third register, A register is initially set to 0.
3. A 1-bit C register is also initialized to 0.
4. Control logic reads the bits of the multiplier (Q) one at a time.
• If it is 1, M is added to the A register and the result is stored. Then all the bits of the C, A, Q registers are shifted to right one bit.
• If it is 0, no addition is performed, just the shift.
5. This process repeated for each bit of the original multiplier.
6. The product is contained in the A and Q registers.

Flowchart for Unsigned Binary Multiplication

TWO'S COMPLEMENT MULTIPLICATION

Booth's Algorithm for Two's Complement Multiplication

Booth's Algorithm (7 x 3)

1. The multiplier and multiplicand are placed in the Q and M registers respectively.
2. A 1-bit register is placed to the right of the LSB of the Q register.
3. A register is initialized to 0.
4. Control logic scans the bits of Q one at a time. The bit to its right is also examined.
• If the 2 bits are same (1-1 or 0-0), then shift all the registers (except M) to the right 1 bit.
• If the 2 bits differ, then M is added to (0-1) or subtracted from (1-0) the A register, follow by the right shift. 
• In either case, the right shift is such that the leftmost bit of A, not only is shifted, but also remains.
5. This process repeated for each bit of the original multiplier.

DIVISION

Flowchart for Unsigned Binary Division

Two's Complement Division (7/3)

1. Load the divisor into the M register. Load the dividend into the A, Q registers. (The dividend is expressed as a 2n-bit positive number.)
2. Shift A, Q left 1 bit position.
3. Subtract M from A.
• If the result is positive, then add 1 to Q.
• If the result is negative, restore the previous value of A.
4. This process repeated for each bit of the original dividend.
5. The remainder is in A and the quotient is in Q.

To do two's complement division, convert the operands into unsigned values and account for the signs by complementation where needed.