Chapter 4:Computer Arithmetic
Computer Architecture
and Organization
Department of Computer Engineering
The Arithmetic & Logic Unit(ALU)
It is the part of the computer that actually performs arithmetic and
logical operations on data
Data are presented to the ALU in registers, and the results of an
operation are stored in registers
These registers are temporary storage locations within the
processor that are connected by signal paths to the ALU
The control unit provides signals that control the operation of the
ALU and the movement of the data into and out of the ALU.
Computer Architecture and Organization 2
ALU Inputs and Outputs block diagram
Computer Architecture and Organization 3
Integer Representation
In computer system only binary digits (0 and 1) used to represent
numbers
If we are limited to non-negative integers, the representation is
straight forward.
In general, if an n-bit sequence of binary digits is
interpreted as an unsigned integer A, its value is
Computer Architecture and Organization 4
Sign-Magnitude Representation
In sign magnitude representation, the most significant (leftmost)
bit in the word is a sign bit and all the right bit next to the sign bit
represent magnitude.
If the sign bit is 0, the number is positive;
If the sign bit is 1, the number is negative
For example the sign magnitude representation of +18 and -18 is:
Exercise: Represent an integer number +32 and -32 using sign
magnitude?
Computer Architecture and Organization 5
Sign-Magnitude Representation Draw backs
One is that addition and subtraction require a consideration of both the
signs of the numbers and their relative magnitudes to carry out the required
operation
Another drawback is that there are two representations of 0:
Because of the above drawbacks, sign-magnitude representation is rarely
used in implementing the integer portion of the ALU
Instead, the most common scheme to represent an integer number is twos
complement representation
Computer Architecture and Organization 6
Twos Complement Representation
Like sign magnitude, twos complement representation uses the
most significant bit as a sign bit
Making it easy to test whether an integer is positive or negative
Key characteristics of twos complement representation and
arithmetic:
Computer Architecture and Organization 7
Twos Complement Representation
Consider an n-bit integer, A, in twos complement representation.
If A is positive, then the sign bit an-1 is zero
The remaining bits represent the magnitude of the number in the
same fashion as for sign magnitude, thus
For negative number A (A<0) the sign bit an-1 is 1, thus
· The range of negative integers that can be represented is
from
· The range of Computer
positiveArchitecture
integers, 0 to
and Organization 8
Twos Complement Representation
The given equation below defines the twos complement
representation for both positive and negative numbers.
The steps in order to represent a decimal number in twos
complement is:
1. Convert the decimal in to binary and represent in sign
magnitude
2. Find 1’s complement of the sign magnitude representation
3. add 1 to the least significant bit from the result obtained step 2
4. Finally, the result is twos complement presentation of a
number
Computer Architecture and Organization 9
Twos Complement representation
Exercise: Represent -18 and +18 using twos complement
representation?
Advantages of two complement in computer arithmetic
One representation of zero
Computer performs arithmetic works easily
Computer Architecture and Organization 10
Twos complement Special Case 1
0 = 00000000
Bitwise not =11111111
Add 1 to LSB +1
Result 1 00000000
Bit 1 at most significant bit is Overflow, so it will be ignored, so:
- 0 = 0 , as a result 0 is represented in single binary using twos
complement
Computer Architecture and Organization 11
Twos Complement Special Case 2
-128 = 10000000
bitwise not= 01111111
Add 1 to LSB +1
Result =10000000, So:
-(-128) = -128 , here we expected the twos complement of
negative number is positive but the result is similar which is un
avoidable for this number only
Computer Architecture and Organization 12
Conversion Between Lengths
It is sometimes desirable to take an n-bit integer and store it in m
bits, where m>n
In sign-magnitude notation, this is easily accomplished:
simply move the sign bit to the new leftmost position and fill
the rest M-n bits in with zeros.
This procedure will not work for twos complement negative
integers
the rule for twos complement integers is to move the sign bit to
the new leftmost position and fill in with copies of the sign bit.
Computer Architecture and Organization 13
Conversion Between Lengths
Sign Magnitude representation conversion example from 8
bit to 16 bit
Twos complement representation conversion example from 8
bit to 16 bit
Computer Architecture and Organization 14
Addition and Subtraction
Addition proceeds as if the two numbers were unsigned integers
If the result of the operation is positive, we get a positive number
in twos complement form, which is the same as in unsigned-integer
form
If the result of the operation is negative, we get a negative number
in twos complement form
In some instances, there is a carry bit beyond the end of the word
(indicated by shading in examples at slide 17), which is ignored
Computer Architecture and Organization 15
Addition and Subtraction
On any addition, the result may be larger than can be held in the
word size being used, this condition is called overflow
When overflow occurs, the ALU must signal this fact so that no
attempt is made to use the result
To detect overflow, the following rule is observed:
OVERFLOW RULE: If two numbers are added, and they are
both positive or both negative, then overflow occurs if and only if
the result has the opposite sign.
Computer Architecture and Organization 16
Addition of Numbers in Twos Complement
Representation Example
Computer Architecture and Organization 17
Subtraction Rule
To subtract one number (subtrahend) from another (minuend),
take the twos complement, (negation) of the subtrahend and add
it to the minuend.
Subtraction of Numbers in Twos Complement Representation (M
-S) example:
Computer Architecture and Organization 18
Block diagram of Hardware for Addition and Subtraction
Computer Architecture and Organization 19
Multiplication
multiplication is a complex operation, whether performed in
hardware or software as compared to addition and subtraction
A wide variety of algorithms have been used in various computers
Multiplication Methods:
UNSIGNED INTEGERS Multiplication:
o Multiplication involves the generation of partial products, one
for each digit in the multiplier
o These partial products are then summed to produce the final
product.
o When the multiplier bit is 0, the partial product is 0.
Computer Architecture and Organization 20
Multiplication
o When the multiplier is 1, the partial product is the
multiplicand.
o The total product is produced by summing the partial products
o The multiplication of two n-bit binary integers results in a
product of up to 2n bits in length(e.g., 11x11=1001)
Multiplication of Unsigned Binary Integers examples:
Computer Architecture and Organization 21
Computerized Unsigned Multiplication
There are several things we can do to make computerized
multiplication more efficient
we can perform a running addition on the partial products rather
than waiting until the end. Why we make these?
Rule:
For each 1 on the multiplier add and shift .
For each 0 on the multiplier only perform shift operation.
Example: 1011 * 1101
M – Multiplicand , Q – Multiplier, A - Partial Accumulator
register
Computer Architecture and Organization
22
Computerized Unsigned Multiplication
C – Carry
IF LSB of Q (Qo) is 1 -> A = A + M and shift to the right -
CAQ
IF LSB of Q (Qo) is 0 -> Just shift to the right - CAQ
The final answer is the value stored in A Q register.
Computer Architecture and Organization
23
Hardware Implementation of Unsigned Binary Multiplication
Computer Architecture and Organization 24
Flowchart for Unsigned Binary Multiplication
Computer Architecture and Organization 25
MULTIPLICATION of Negative Numbers
Straight forward multiplication will not work for signed numbers
If both the multiplicand and multiplier are negative or either of the two
negative
If We multiplied unsigned 11 (1011) by 13 (1101) to get 143 (10001111).
If we interpret these as twos complement numbers, we have -5 (1011)
times -3 (1101) equals -113 (10001111) but we expected to obtain +15 so,
Solution 1
Convert both multiplicand and multiplier to positive
Multiply as unsigned integer
Make the result twos complement, if and only if the sign of original
numbers different
Solution 2
Use Booth’s algorithm
Computer Architecture and Organization
26
Booth’s algorithm
An algorithm which is used for multiplication of negative
number which not require final transformation step
Speeding up the multiplication process, relative to a more
straightforward approach
The multiplier and multiplicand are placed in the Q and M
registers respectively
There is also a 1-bit register placed logically to the right of
the least significant bit of Q register and represented as Q-1
The results of the multiplication will appear in the A and Q
registers.
A and Q-1 are initialized to 0 at the starting of Operation
Computer Architecture and Organization
27
Booth’s algorithm
When we perform right shift An-1 not only shifted to An-2 position
but also remain at An-1 to preserve the sign of numbers In A and Q
Flowchart of Booth’s Algorithm:
Computer Architecture and Organization
28
Example of Booth’s Algorithm
Computer Architecture and Organization 29
Division of Unsigned Binary Integers
Some what more complex than multiplication but is based on the
same general principle
The operation involves repetitive shifting and addition or subtraction.
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
Computer Architecture and Organization 30
Division of Unsigned Binary Integers
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
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
Computer Architecture and Organization 31
Division of Unsigned Binary Integers Examples
Computer Architecture and Organization 32
Flowchart for Unsigned Binary Division
Computer Architecture and Organization 33
Flowchart Description
The divisor is placed in the M register, the dividend in the Q register
At each step, the A and Q registers together are shifted to the left 1
bit
M is subtracted from A to determine whether A divides the partial
remainder
If it does, then Q0 gets a 1 bit. Otherwise,Q0 gets a 0 bit and M must
be added back to A to restore the previous value
The count is then decremented, and the process continues for n steps
At the end, the quotient is in the Q register and the remainder is in
the A register
Computer Architecture and Organization 34
Division of signed binary number algorithm
Division of unsigned binary with some difficulty, be extended to
negative numbers
The algorithm assumes that the divisor V and the dividend D are
positive and |V|<|D|
If |V|=|D|, then the quotient Q=1 and Remainder R=0
If |V|>|D|, then the quotient Q=0 and Remainder R=D
The algorithm can be summarized as follows:
1. Load the twos complement of the divisor into the M register; that is,
the M register contains the negative of the divisor. Load the dividend
into the A, Q registers. The dividend must be expressed as a 2n-bit
Computer Architecture and Organization 35
Division of signed binary number algorithm
positive number. Thus, for example, the 4-bit 0111 becomes 00000111.
2. Shift A, Q left 1 bit position.
3. Perform This operation AA-M subtracts the divisor from the
contents of A.
Computer Architecture and Organization 36
Signed Division
To deal with negative numbers, we recognize that the remainder
is defined by This is because the remainder is defined by
Consider the following examples of integer division with all
possible combinations of signs of D and V:
Computer Architecture and Organization 37
Signed Division
The signs of Q and R are easily derivable from the signs of D and
V, thus
one way to do twos complement division is to convert the
operands into unsigned values and, at the end, to account for the
signs by complementation where needed
Computer Architecture and Organization 38
Example of Restoring Twos Complement Division (7/3)
Computer Architecture and Organization 39
End of Chapter 4
Computer Architecture
and Organization
Department of Computer Engineering
