ARITHMETIC FOR COMPUTERS

INTEGER REPRESENTATION
⚫ In the binary number system arbitrary numbers can be
represented with zero and one, the minus sign, and the
period, or radix point
-1101.01012 = -13.312510

For purposes of computer storage and processing we do

not have the benefit of minus signs and periods
Only have 0 & 1 to represent everything
An 8-bit word can represent the numbers from 0 to 255
An n-bit sequence of binary digits is interpreted as an
unsigned integer A,
SIGN-MAGNITUDE REPRESENTATION
Most significant (leftmost) bit in the word as a sign bit
⚫ Sign bit is 0, the number is positive
⚫ Sign bit is 1, the number is negative
n-bit word, the rightmost n-1 bits hold the magnitude
of the integer

Drawbacks
⚫ Need to consider both sign and magnitude in arithmetic
⚫ There are two representations of 0
2S COMPLIMENT REPRESENTATION
Like sign magnitude, twos complement representation
uses the most significant bit as a sign bit
The number zero is identified as positive and therefore has
a 0 sign bit and a magnitude of all 0s
Range of positive integers 0 through 2n-1 – 1
Largest positive number is a 0 followed by all 1s = 2n-1 – 1
2S COMPLIMENT REPRESENTATION (2)
Range of negative integers -1 through -2n-1
2s compliment representation
⚫ an-1 = 0 defines a positive number
⚫ an-1 = 1 the term 2n-1 subtracted from the summation
yielding a negative number
Almost universally used as the processor
representation for integers
Conversion between binary and decimal
SIGN MAGNITUDE AND 2S COMPLIMENT
REPRESENTATION
Converting between different length
⚫ In sign-magnitude notation simply move the sign bit to
the new leftmost position and fill in with zeros
⚫ In twos complement move the sign bit to the new
leftmost position and fill in with copies of the sign bit
INTEGER ARITHMETIC
Negation
 INTEGER ARITHMETIC (2)
Addition and Subtraction
Addition of Numbers in Twos Complement Representation
Overflow - On any addition, the result may be larger than
can be held in the word size being used
ADDITION AND SUBTRACTION (2)
Subtraction
GEOMETRIC DEPICTION OF 2S COMPLIMENT
A2sRITHMETIC
complement of any number is horizontally opposite that number (indicated
by dashed horizontal lines)
Starting at any number on the circle, we can add positive k (or subtract
negative k) to that number by moving k positions clockwise, and we can
subtract positive k (or add negative k) from that number by moving k positions
counterclockwise
If an arithmetic operation results in traversal of the point where the endpoints
are joined, an incorrect answer is given (overflow)
BLOCK DIAGRAM OF HARDWARE FOR ADDITION
AND SUBTRACTION
The binary adder treats the two numbers as unsigned
integers
For addition, the two numbers are presented to the adder
from two registers, designated in this case as A and B
registers
The result may be stored in one
of these registers or in a third
The overflow indication is stored
in a 1-bit overflow flag (OF)
(0- No overflow; 1- Overflow)
For subtraction, the subtrahend
(B register) is passed through a
2s complementer so that its twos
complement is presented to the
adder
MULTIPLICATION
Complex
Variety of algorithms
Multiplication of unsigned integers
⚫ Generation of partial products - one for each digit in the
multiplier
⚫ Shift each successive partial product one position to the
left relative to the preceding partial product
⚫ Sum partial products for final product
⚫ The multiplication of two n-bit binary integers results in
a product of up to 2n bits in length
MULTIPLICATION (2)
Performing a running addition on the partial products
rather than waiting until the end
⚫ Eliminates the need for storage of all the partial
products
⚫ Fewer registers are needed
⚫ Save some time on the generation of partial
products
For each 1 on the multiplier perform add and a shift
operation
For each 0, only a shift is required
MULTIPLICATION OF UNSIGNED INTEGERS
Block diagram for Unsigned Binary Multiplication

Flowchart for Unsigned Binary

Multiplication
C - holds a carry bit resulting from
addition
2S COMPLEMENT MULTIPLICATION
Adding 9 (1001) plus 3 (0011) to get 12 (1100)
As twos complement integers, we are adding -7 (1001) to 3
(0011) to get -4 (1100)
Multiplied 11 (1011) by 13 (1101) to get 143 (10001111)
If we interpret these as 2s complement numbers, we have
-5 (1011) times -3 (1101) equals -113 (10001111)
Any unsigned binary number can be expressed as a sum of
powers of 2
Multiplication of a binary number by 2n is accomplished by
shifting that number to the left n bits
Viewing partial products as 2n-bit numbers generated from
the n-bit multiplicand
2S COMPLEMENT MULTIPLICATION (2)

Each partial product (other than that for 20) consists of

this number shifted to the left, with the unoccupied
positions on the right filled with zeros

Multiplication of Two Unsigned 4-Bit

Integers
COMPARISON OF MULTIPLICATION OF UNSIGNED AND 2S
COMPLEMENT INTEGERS
Each partial product must be a negative 2s complement
number of 2n (8) bits
Note that this is accomplished by padding out each partial
product to the left with binary 1s

If the multiplier is also negative, straightforward

multiplication will not work
MULTIPLYING NEGATIVE NUMBERS
Solution 1
⚫ Convert to positive if required
⚫ Multiply as above
⚫ If signs were different, negate answer
Solution 2
⚫ Booth’s algorithm
 BOOTH’S ALGORITHM
Relatively faster than straightforward approach

1-bit register Q-1 placed logically to

the right of LSB of the Q register
(multiplier)
Multiplication result appear in the A
and Q registers
A and Q are initialized to 0.
Control logic scans the bits of the
multiplier one at a time. The bit to its
right is also examined.
If the two bits are the same (1–1 or
0–0), then all of the bits of A,Q, and
Q-1registers are shifted to the right 1
bit
 BOOTH’S ALGORITHM

Q0 -> Q-1 ; 0 -> 1 Add ; 1 -> 1 Subtract

Right shift after addition or subtraction.
An-1 not only shifted into An-2. But also remains in An-1.
Arithmetic shift preserve the sign of the number in A and
EXAMPLES USING BOOTH’S ALGORITHM
DIVISION
More complex than multiplication
Negative numbers are really bad!
Based on long division
Operation involves repetitive shifting and addition or
subtraction
First, check the divisor able to divide the number
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
Until this event occurs, 0s are placed in the quotient from
left to right
From this point the division follows a cyclic pattern
When the event occurs, a 1 is placed in the quotient and
the divisor is subtracted from the partial dividend.
DIVISION OF UNSIGNED BINARY INTEGER
RESTORING ALGORITHM
1. Load the twos complement of the divisor into the M
register;
Load the dividend into the A, Q registers
The dividend must be expressed as a 2n-bit positive
number
Example, the 4-bit 0111 becomes 00000111
1001 becomes 11111001
2. Shift A, Q left 1 bit position
3. Perform A <- A - M
4. a. If the result is nonnegative then set Q0 <- 1
b. If the result is negative then set Q0 <- 0 and restore the
previous value of A
5. Repeat steps 2 through 4 as many times as there are bit
FLOWCHART FOR UNSIGNED BINARY DIVISION
BINARY DIVISION (1)
FIXED POINT REPRESENTATION
The number of digits before and after the decimal point
is set
Binary representation of 1.625 would be 1.101(2)
A 32- bit fixed-point representation might allocate 24
bits for the integer part and 8 bits for the fractional
part

32-bit representation of 1.625

00000000 00000000 00000001 . 10100000
FLOATING POINT
3,155,760,000ten or 3.15576ten × 109
Scientific notation
Has a single digit to the left of the decimal point
Normalized number,
⚫ A number in scientific notation that has no
leading 0s is called
1.0ten × 10-9 is in normalized scientific notation
0.1ten × 10-8 and 10.0ten × 10-10 are not
Binary numbers in scientific notation: 1.0two × 2-1
Binary point
FLOATING POINT REPRESENTATION
There is no fixed number of digits before and after the
decimal point
The decimal point can float
Slower and less accurate than fixed-point representations
Can handle a larger range of numbers
Represention are just approximations
One of the challenges in programming with floating-point
values is ensuring that the approximations lead to
reasonable results
Small discrepancies in the approximations can magnify to
the point where the final results become meaningless
Requires a great deal of computing power
FLOATING POINT REPRESENTATION
For decimal numbers, 976,000,000,000,000 can be
represented as 9.76 X 1014 and 0.0000000000000976 can
be represented as 9.76 X 10-14
Dynamically slide the decimal point to a convenient
location and use the exponent of 10 to keep track of that
decimal point
This allows a range of very large and very small numbers
to be represented with only a few digits
This same approach can be taken with binary numbers.
We can represent a number in the form (-1)S X F X 2E
Number can be stored in a binary word with three fields
⚫ S – Sign plus or minus
⚫ F Fraction/Significand
⚫ E Exponent
 32-BIT FLOATING POINT FORMAT

The leftmost bit stores the sign of the number (0 –> +ve , 1 –>
-ve)
The exponent value is stored in the next 8 bits
Biased representation - A fixed value, called the bias, is
subtracted from the field to get the true exponent value
The bias equals 2k-1-1 where k - # of bits in the binary
exponent
32-BIT FLOATING POINT FORMAT (2)

With a bias of 127 the true exponent values are in the

range -127 to +128
The final portion of the word (23 bits in this case) is the
significand (Fraction)
The first bit of the true significand is always 1 and need
not be stored in the significand field
The value 127 is added to the true exponent to be stored
in the exponent field
The base is 2
NORMALIZED NUMBER
Normalized number one in which the most significant
digit of the significand is nonzero
For base 2 representation, a normalized number is
therefore one in which the most significant bit of the
significand is one
Given a number that is not normalized, the number may
be normalized by shifting the radix point to the right of
the leftmost 1 bit and adjusting the exponent accordingly

Normalized nonzero number is one in the form

EXPRESSIBLE NUMBERS IN TYPICAL 32-BIT
FORMATS
EXPRESSIBLE NUMBERS IN TYPICAL 32-BIT
FORMATS (2)
Five regions on the number line are not included in these
ranges:
⚫ Negative numbers less than called negative overflow
⚫ Negative numbers greater than called negative
underflow
⚫ Zero
⚫ Positive numbers less than called positive underflow
⚫ Positive numbers greater than called positive overflow
Actual floating-point representations include a special bit
pattern to designate zero
Overflow occurs when an arithmetic operation results in a
magnitude greater than can be expressed with an exponent of
128 (e.g., 2220)
Underflow occurs when the fractional magnitude is too small
(e.g.,2-220 )
DENSITY OF FLOATING NUMBER
The numbers represented in floating-point notation are not
spaced evenly along the number line
The possible values get closer together near the origin and farther
apart as you move a away
Many calculations produce results are not exact
Have to be rounded to the nearest value that the notation can
represent
Trade-off between range and precision
⚫ 8 bits devoted to the exponent and 23 to the significand
⚫ If we increase the number of bits in the exponent, we expand
the range of expressible numbers
⚫ Only a fixed number of different values can be expressed, we
have reduced the density of those numbers and therefore the
precision
⚫ The only way to increase both range and precision is to use
more bits
IEEE STANDARD FOR BINARY FLOATING POINT
REPRESENTATION
Defined in IEEE Standard 754, adopted in 1985
Facilitate the portability of programs from one processor
to another and to encourage the development of
sophisticated, numerically oriented programs
The standard has been widely adopted and is used on
virtually all contemporary processors and arithmetic
coprocessors
IEEE 754 format
IEEE STANDARD FOR BINARY FLOATING POINT
REPRESENTATION
Extended Precision
The extended formats include additional bits in the exponent
(extended range) and in the significand (extended precision)
Used for intermediate calculations
With their greater precision, the extended formats lessen
⚫ The chance of a final result that has been contaminated by excessive roundoff
error; with their greater range
⚫ Also lessen the chance of an intermediate overflow
An additional motivation for the single extended format is that it
affords some of the benefits of a double format without incurring the
time penalty usually associated with higher precision
IEEE FORMAT
FLOATING POINT ARITHMETIC
For addition and subtraction, it is necessary to ensure that
both operands have the same exponent value
This may require shifting the radix point on one of the
operands to achieve alignment
Multiplication and division are more straightforward
FLOATING POINT ARITHMETIC (2)
A floating-point operation may produce one of these conditions:
Exponent overflow:
⚫ A positive exponent exceeds the maximum possible exponent
value
Exponent underflow:
⚫ A negative exponent is less than the minimum possible
exponent value (e.g., 2-200 is less than 2-127)
⚫ The number is too small to be represented, and it may be
reported as 0
Significand underflow:
⚫ In the process of aligning significands, digits may flow off the
right end of the significand
Significand overflow:
⚫ The addition of two significands of the same sign may result
in a carry out of the most significant bit
ADDITION AND SUBTRACTION
Need for alignment
More complex than multiplication and division
Four basic phases of the algorithm
⚫ Check for zeros
⚫ Align the significands
⚫ Add or subtract the significands
⚫ Normalize the result
Zero check
⚫ Addition and subtraction are identical except for a sign change, the
process begins by changing the sign of the subtrahend if it is a
subtract operation
⚫ If either operand is 0, the other is reported as the result
Significand alignment
⚫ The next phase is to manipulate the numbers so that the two
exponents are equal
⚫ Alignment is achieved by repeatedly shifting the magnitude portion
of the significand right 1 digit and incrementing the exponent until
ADDITION AND SUBTRACTION (2)
Addition
⚫ The two significands are added together, taking into
account their signs.
⚫ Because the signs may differ, the result may be 0
⚫ There is also the possibility of significand overflow by 1
digit. If so, the significand of the result is shifted right
and the exponent is incremented.
⚫ An exponent overflow could occur as a result; this
would be reported and the operation halted
Normalization
⚫ Normalization consists of shifting significand digits left
until the most significant digit is nonzero
⚫ Each shift causes a decrement of the exponent and thus
could cause an exponent underflow.
⚫ Finally, the result must be rounded off
FLOATING POINT ADDITION
Match the exponent
Add the significant
Normalize the sum
Round the sum
 BLOCK DIAGRAM OF AN ARITHMETIC UNIT DEDICATED TO
FLOATING-POINT ADDITION
Small ALU subtract the
exponent of one operand from
the other and determine which is
larger and by how much
This difference controls the three
multiplexors;
Select the larger exponent, the
significand of the smaller
number, and the significand of
the larger number
The smaller significand is
shifted right, and then the
significands are added together
using the big ALU
The normalization step then
shifts the sum left or right and
increments or decrements the
exponent
Rounding then creates the final
FLOATING-POINT MULTIPLICATION (Z=X * Y)
FLOATING-POINT DIVISION (Z=X/Y)