Introduction

[Link]/docs/microprocessor-and-computer-architecture/computer-arithmetic/introduction

BimStudies February 10, 2024

Here is the key Introduction of Computer Arithmetic:

Computer arithmetic specifically refers to the design and implementation of arithmetic

operations within the central processing unit (CPU) and associated hardware
components.

• It involves the representation of numerical data, execution of arithmetic operations, and

the handling of related issues such as precision, overflow, and speed optimization.

• An arithmetic processor is the part of a processor unit that executes arithmetic

operations.

The four basic arithmetic operations are:

Note:
• The arithmetic processor is very simple if only a binary fixed-point add instruction is
included.

• The arithmetic processor would be more complicated if it includes all four arithmetic
operations for binary and decimal data in fixed-point and floating-point representation.

Points to be Remembered:

Negative Number Representation:

Sign Magnitude:

Sign magnitude is a very simple representation of negative numbers. In sign magnitude

the first bit is dedicated to represent the sign and hence it is called sign bit.

1/2
→ Sign bit ‘1’ represents negative sign.

→ Sign bit ‘0’ represents positive sign.

In sign magnitude representation of a n – bit number, the first bit will represent sign and
rest n-1 bits represent magnitude of number.

For example:
+25 = 011001

Where 11001 = 25

And 0 for ‘+’

-25 = 111001

Where 11001 = 25

But there is one problem in sign magnitude and that is we have two representations of 0

+0 = 000000

– 0 = 100000

2’s complement method

To represent a negative number in this form, first we need to take the 1’s complement of
the number represented in simple positive binary form and then add 1 to it.

For example:
(-8)10 = (1000)2

1’s complement of 1000 = 0111

Adding 1 to it, 0111 + 1 = 1000

So, (-8)10 = (1000)2

2/2
Addition and Subtraction
[Link]/docs/microprocessor-and-computer-architecture/computer-arithmetic/addition-and-subtraction

February 10, 2024

There are three ways of representing negative fixed-point binary numbers:

• Most computers use the signed-2`s complement representation when performing

arithmetic operations with integers.

• For floating-point operations, most computers use the signed-magnitude

representation for the mantissa.

Note:
• It is important to realize that the adopted representation for negative numbers refers to
the representation of numbers in the registers before and after the execution of the
arithmetic operation.

Rules for Addition & Subtraction Algorithm with Signed-Magnitude

Data:
1. When the signs (+,-) of A and B are same, add the two magitudes and attach the sign
of A to the result.

2. When the signs (+,-) of A and B are different, compare the magnitudes and subtract the
smaller number from the larger.

If A>B, use the sign of A

If A<B, use the sign of B
If A=B, subtract B from A and make the sign positive

1/2
Flowchart for Add and Subtract Operation:

2/2
Computer Organization and Architecture Chapter 5 : Computer Arithmetic

B Register A Register

Complement

Switch

B7
XOR
n bit Adder
B8

V Z S C / n bit

B7

Multiplication Algorithm
Check for Zero
Fig: Block diagram of hardware for addition / subtraction

5.3 Multiplication Algorithm

The multiplier and multiplicand bits are loaded into two registers Q and M. A third register A is
initially set to zero. C is the 1-bit register which holds the carry bit resulting from addition. Now,
the control logic reads the bits of the multiplier one at a time. If Q0 is 1, the multiplicand is added
to the register A and is stored back in register A with C bit used for carry. Then all the bits of
CAQ are shifted to the right 1 bit so that C bit goes to An-1, A0 goes to Qn-1 and Q0 is lost. If Q0 is
0, no addition is performed just do the shift. The process is repeated for each bit of the original
multiplier. The resulting 2n bit product is contained in the QA register.

Fig: Block diagram of multiplication

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 3

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

There are three types of operation for multiplication.

 It should be determined whether a multiplier bit is 1 or 0 so that it can designate the
partial product. If the multiplier bit is 0, the partial product is zero; if the multiplier bit is
1, the multiplicand is partial product.
 It should shift partial product.
 It should add partial product.

Unsigned Binary Multiplication

1011 Multiplicand 11
X 1101 Multiplier 13
1011
0000 Partial Product
1011
+ 1011
10001111 Product (143)

Start

M ß Multiplicand, Q ß Multiplier
C, A ß 0, Count ß No. of bits of Q

Is
No Yes
Q0 = 1 AßA+M
?

Right Shift C, A, Q
Count ß Count - 1

Is
No
Count = 0
?
Yes
Stop Result in AQ
Fig. : Flowchart of Unsigned Binary Multiplication

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 4

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Example: Multiply 15 X 11 using unsigned binary method

C A Q M Count Remarks
0 0000 1011 1111 4 Initialization

0 1111 1011 - - Add (A ß A + M)

0 0111 1101 - 3 Logical Right Shift C, A, Q

1 0110 1101 - - Add (A ß A + M)

0 1011 0110 - 2 Logical Right Shift C, A, Q

0 0101 1011 - 1 Logical Right Shift C, A, Q

1 0100 1011 - - Add (A ß A + M)

0 1010 0101 - 0 Logical Right Shift C, A, Q

Result = 1010 0101 = 27 + 25 + 22 + 20 = 165

Alternate Method of Unsigned Binary Multiplication

Start

X ß Multiplicand, Y ß Multiplier
Sum ß 0, Count ß No. of bits of Y

Is
No Yes
Y0 = 1 Sum ß Sum + X
?

Left Shift X, Right

Shift Y
Count ß Count - 1

Is
No
Count = 0
?
Yes
Stop Result in Sum
Fig: Unsigned Binary Multiplication Alternate method

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 5

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Algorithm:
Step 1: Clear the sum (accumulator A). Place the multiplicand in X and multiplier in Y.
Step 2: Test Y0; if it is 1, add content of X to the accumulator A.
Step 3: Logical Shift the content of X left one position and content of Y right one position.
Step 4: Check for completion; if not completed, go to step 2.

Example: Multiply 7 X 6
Sum X Y Count Remarks
000000 000111 110 3 Initialization

000000 001110 011 2 Left shift X, Right Shift Y

001110 011100 001 1 Sum ß Sum + X,

Left shift X, Right Shift Y
101010 111000 000 0 Sum ß Sum + X,
Left shift X, Right Shift Y

Result = 101010 = 25 + 23 + 21 = 42

Signed Multiplication (Booth Algorithm) – 2’s Complement Multiplication

Multiplier and multiplicand are placed in Q and M register respectively. There is also one bit
register placed logically to the right of the least significant bit Q0 of the Q register and designated
as Q-1. The result of multiplication will appear in A and Q resister. A and Q-1 are initialized to
zero if two bits (Q0 and Q-1) are the same (11 or 00) then all the bits of A, Q and Q-1 registers are
shifted to the right 1 bit. If the two bits differ then the multiplicand is added to or subtracted from
the A register depending on weather the two bits are 01 or 10. Following the addition or
subtraction the arithmetic right shift occurs. When count reaches to zero, result resides into AQ
in the form of signed integer [-2n-1*an-1 + 2n-2*an-2 + …………… + 21*a1 + 20*a0].

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 6

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Start

Initialize A ß 0, Q-1 ß 0,
M ß Multiplicand, Q ß Multiplier,
Count ß No. of bits of Q

Is
= 10 = 01
AßA-M Q0Q-1 AßA+M
?

= 11
= 00
Arithmetic Shift Right
A, Q, Q-1
Count ß Count - 1

Is
No
Count = 0
?
Yes
Stop Result in AQ

Fig.: Flowchart of Signed Binary Numbers (using 2’s Complement, Booth Method)

Example: Multiply 9 X -3 = -27 using Booth Algorithm

+3 = 00011, -3 = 11101 (2’s complement of +3)
A Q Q-1 Add (M) Sub ( M +1) Count Remarks
00000 11101 0 01001 10111 5 Initialization

10111 11101 0 - - - Sub (A ß A - M) as Q0Q-1 = 10

11011 11110 1 - - 4 Arithmetic Shift Right A, Q, Q-1

00100 11110 1 - - - Add (A ß A + M) as Q0Q-1 = 01

00010 01111 0 - - 3 Arithmetic Shift Right A, Q, Q-1

11001 01111 0 - - - Sub (A ß A - M) as Q0Q-1 = 10

11100 10111 1 - - 2 Arithmetic Shift Right A, Q, Q-1

11110 01011 1 - - 1
Arithmetic Shift Right A, Q, Q-1
as Q0Q-1 = 11
11111 00101 1 - - 0 Arithmetic Shift Right A, Q, Q-1
as Q0Q-1 = 11
9 8 7 6 5 2 0
Result in AQ = 11111 00101 = -2 +2 +2 +2 +2 +2 +2 = -512+256+128+64+32+4+1 = -27

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 7

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

5.4 Division Algorithm

Division is somewhat more than multiplication but is based on the same general principles. The
operation involves repetitive shifting and addition or subtraction.

First, the bits of the dividend are examined from left to right, until the set of bits examined
represents a number greater than or equal to the divisor; this is referred to as the divisor being
able to divide the number. Until this event occurs, 0s are placed in the quotient from left to right.
When the event occurs, a 1 is placed in the quotient and the divisor is subtracted from the partial
dividend. The result is referred to as a partial remainder. The division follows a cyclic pattern.
At each cycle, additional bits from the dividend are appended to the partial remainder until the
result is greater than or equal to the divisor. The divisor is subtracted from this number to
produce a new partial remainder. The process continues until all the bits of the dividend are
exhausted.

Shift Left

An An-1 ………… A0 Qn-1 ………… Q0

Add / Subtract
Control Unit

N+1 Bit
Adder

0 Mn-1 ………… M0 Divisor

Fig.: Block Diagram of Division Operation

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 8

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Restoring Division (Unsigned Binary Division)

Algorithm:
Step 1: Initialize A, Q and M registers to zero, dividend and divisor respectively and counter to n
where n is the number of bits in the dividend.
Step 2: Shift A, Q left one binary position.
Step 3: Subtract M from A placing answer back in A. If sign of A is 1, set Q0 to zero and add M
back to A (restore A). If sign of A is 0, set Q0 to 1.
Step 4: Decrease counter; if counter > 0, repeat process from step 2 else stop the process. The
final remainder will be in A and quotient will be in Q.

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 9

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Example: Divide 15 (1111) by 4 (0100)

A Q M M +1 Count Remarks
00000 1111 00100 11100 4 Initialization

00001 111□ - - - Shift Left A, Q

11101 111□ - - - Sub (A ß A – M)
00001 1110 - - 3 Q0 ß 0, Add (Aß A + M)

00011 110□ - - - Shift Left A, Q

11111 110□ - - - Sub (A ß A – M)
00011 1100 - - 2 Q0 ß 0, Add (Aß A + M)

00111 100□ - - - Shift Left A, Q

00011 100□ - - - Sub (A ß A – M)
00011 1001 - - 1 Set Q0 ß 1

00111 001□ - - - Shift Left A, Q

00011 001□ - - - Sub (A ß A – M)
00011 0011 - - 0 Set Q0 ß 1
Quotient in Q = 0011 = 3
Remainder in A = 00011 = 3

Non – Restoring Division (Signed Binary Division)

Algorithm
Step 1: Initialize A, Q and M registers to zero, dividend and divisor respectively and count to
number of bits in dividend.
Step 2: Check sign of A;
If A < 0 i.e. bn-1 is 1
a. Shift A, Q left one binary position.
b. Add content of M to A and store back in A.
If A ≥ 0 i.e. bn-1 is 0
a. Shift A, Q left one binary position.
b. Subtract content of M to A and store back in A.
Step 3: If sign of A is 0, set Q0 to 1 else set Q0 to 0.
Step 4: Decrease counter. If counter > 0, repeat process from step 2 else go to step 5.
Step 5: If A ≥ 0 i.e. positive, content of A is remainder else add content of M to A to get the
remainder. The quotient will be in Q.

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 10

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Start

Initialize: A ß 0, M ß Divisor,
Q ß Dividend, Count ß No. of bits of Q

Is
No Yes
Left Shift AQ A<0 Left Shift AQ
?

AßA+M AßA-M

Is
No Yes
Q0 ß 1 A<0 Q0 ß 0
?

Count ß Count - 1

Is
Yes
Count > 0
?
No

Is
Yes No
A>0 AßA+M
?
Quotient in Q
Remainder in A
Stop

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 11

Computer Organization and Architecture Chapter 5 : Computer Arithmetic

Example: Divide 1110 (14) by 0011 (3) using non-restoring division.

A Q M M +1 Count Remarks
00000 1110 00011 11101 4 Initialization

00001 110□ - - - Shift Left A, Q

11110 110□ - - - Sub (A ß A – M)
11110 1100 - - 3 Set Q0 to 0

11101 100□ - - - Shift Left A, Q

00000 100□ - - - Add (A ß A + M)
00000 1001 - - 2 Set Q0 to 1

00001 001□ - - - Shift Left A, Q

11110 001□ - - - Sub (A ß A – M)
11110 0010 - - 1 Set Q0 to 0

11100 010□ - - - Shift Left A, Q

11111 010□ - - - Add (A ß A + M)
11111 0100 - - 0 Set Q0 to 0
00010 0100 - - - Add (A ß A + M)
Quotient in Q = 0011 = 3
Remainder in A = 00010 = 2

Compiled By: Er. Hari Aryal [haryal4@[Link]] Reference: W. Stallings | 12

Difference between Restoring and Non-Restoring Division Algorithm:

Restoring division Non-restoring division

How it Restores partial remainders Adjusts without restoring partial

works during the process remainders

Speed Slower than non-restoring Faster than restoring division

division

Complexity More complex than non- Less complex than restoring division
restoring division

Operations Requires extra steps to Uses addition and subtraction operations

restore the original result instead of restoring
after a failed subtraction

Divide Overflow
Divide overflow occurs when the divisor value is 0' i.e any dividend being divided by zero
results in Divide Overflow. It can also happen if the resulting quotient is too large to be
fit into the variable defined in the program. Divide overflow generates an exception in the
hardware.