Number Representation
BINARY
ARITHMETIC
Bernhard Kainz (with thanks to A. Gopalan, N. Dulay and E.
Edwards)
b.kainz@imperial.ac.uk
mailto:b.kainz@imperial.ac.uk
Binary Arithmetic
• Unsigned
• Addition, Subtraction, Multiplication and Division
• Signed
• Two’s Complement Addition, Subtraction, Multiplication and
Division
• Chosen because of its widespread use
Binary Arithmetic
• Couple of definitions
• Subtrahend: what is being subtracted
• Minuend: what it is being subtracted from
• Example: 612 – 485 = 127
• 485 is the subtrahend, 612 is the minuend, 127 is the result
Binary Addition – Unsigned
• Reasonably straight forward
• Example: Perform the binary addition 111011 + 101010
Carry 1 1 1 1
A 1 1 1 0 1 1
B + 1 0 1 0 1 0
Sum 1 1 0 0 1 0 1
Step 7 6 5 4 3 2 1
In Decimal: 59 + 42 = 101
Binary Subtraction – Unsigned
• Reasonably straight forward as well
• Example: Perform the binary subtraction 1010101 – 11100
A’’ 0 1 10
A’ 1 0 0 10
A 1 0 1 0 1 0 1
B – 1 1 1 0 0
Diff 0 1 1 1 0 0 1
Step 7 6 5 4 3 2 1
Step k Ak– Bk = Diffk
1 1 – 0 = 1
2 0 –0 = 0
3 1 – 1 = 0
4 0 – 1 Borrow by subtracting 1 from A7..5=101 to
give A’7..5=100 and A’4=10.
Now use A’ instead of A, e.g. A’4 – B4
10 – 1 =1
5 0 – 1 Subtract 1 from A’7..6 =10 to give A’’7..6
=01, A’’5 = 10.
Now use A’’ instead of A’, e.g. A’’5 – B5
10 – 1 =1
6 1 – 0 = 1 i.e. A’’6 – B6
7 0 – 0 = 0
Binary Multiplication – Unsigned
• Example: Perform the binary multiplication 11101 x 111
A 1 1 1 0 1
B x 1 1 1
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
Answer 1 1 0 0 1 0 1 1
Carry 1 10 10 1 1
Binary Division – Unsigned
• Recall:
• Division is:
• Or:
• Left as an exercise
• Can use long division
dividend
divisor
quotient
remainder
divisor
dividend quotient divisor remainder
Binary Arithmetic – Signed
• Two’s complement Arithmetic because of it’s widespread use
• Recall
• Addition and subtraction in two’s complement works without having a
separate sign bit
• Overflow
• Result of an arithmetic operation is too large or too small to fit into the
resultant bit-group (E.g.: 9 can’t fit into 4-bits in Two’s complement)
• Normally left to programmer to deal with this situation
Two’s Complement – Addition
• Add the values and discard any carry-out bit
• Example: Add −8 to +3 and -2 and -5 using 8-bit two’s
complement
(+3) 0000 0011 (–2) 1111 1110
+(–8) 1111 1000 +(–5) 1111 1011
(–5) 1111 1011 (–7) 1 1111 1001
Discard Carry-Out
Two’s Complement – Addition
• Overflow
• Occurs if and only if 2 Two’s Complement numbers are added and
they both have the same sign (both positive or both negative) and
the result has the opposite sign
• Adding two positive numbers must give a positive result
• Adding two negative numbers must give a negative result
• Never occurs when adding operands with different signs
• E.g.
• (+A) + (+B) = -C
• (-A) + (-B) = +C
Two’s Complement – Addition
• Overflow
• Example: Using 4-bit Two’s Complement numbers (−8 ≤ x ≤ +7),
calculate (-7) + (-6)
(–7) 1001
+(–
6)
1010
(+3) 1 0011 “Overflow”
Two’s Complement – Subtraction
• Accomplished by negating the subtrahend and adding it to
the minuend
• Any carry-out bit is discarded
• Example: Calculate 8 – 5 using an 8-bit two’s complement
representation
• Recall: 8 – 5 8 + (- 5)
(+8) 0000 1000 0000 1000
–(+5) 0000 0101 -> Negate -> + 1111 1011
(+3) 1 0000 0011
Discard
Two’s Complement – Subtraction
• Overflow
• Occurs if and only if 2 two’s complement numbers are subtracted,
and their signs are different, and the result has the same sign as
the subtrahend
• E.g.
• (+A) – (–B) = –C
• (–A) – (+B) = +C
Two’s Complement – Subtraction
• Overflow
• Example: Using 4-bit Two’s Complement numbers (−8 ≤ x ≤ +7),
calculate 7 – (-6)
(+7) 0111
–(–6) 0110 (Negated)
(–3) 1101 “Overflow”
(+7) 0111
–(–6) 1010
Two’s Complement – Summary
• Addition
• Add the values, discarding any carry-out bit
• Subtraction
• Negate the subtrahend and add, discarding any carry-out bit
• Overflow
• Adding two positive numbers produces a negative result
• Adding two negative numbers produces a positive result
• Adding operands of unlike signs never produces an overflow
• Note – discarding the carry out of the most significant bit during
Two’s Complement addition is a normal occurrence, and does not
by itself indicate overflow
Two’s Complement – Multiplication and
Division
• Cannot be accomplished using the standard technique
• Example: consider X * (–Y)
• Two’s complement of –Y is 2n–Y X * (Y) = X * (2n–Y) = 2nX –
XY
• Expected result should be 22n – XY
Signed multiplication
• Booth’s multiplication algorithm
• Let m and r be the multiplicand and multiplier, respectively; and
let x and y represent the number of bits in m and r.
• Determine the values of A and S, and the initial value of P. All of these numbers
should have a length equal to (x + y + 1).
• A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with
zeros.
• S: Fill the most significant bits with the value of (−m) in two’s complement notation. Fill the
remaining (y + 1) bits with zeros.
• P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the
least significant (rightmost) bit with a zero.
• Determine the two least significant (rightmost) bits of P.
• If they are 01, find the value of P + A. Ignore any overflow.
• If they are 10, find the value of P + S. Ignore any overflow.
• If they are 00, do nothing. Use P directly in the next step.
• If they are 11, do nothing. Use P directly in the next step.
• Arithmetically shift the value obtained in the 2nd step by a single place to the
right. Let P now equal this new value.
• Repeat steps 2 and 3 until they have been done y times.
• Drop the least significant (rightmost) bit from P. This is the product of m and r.
Booth’s multiplication example
• Find 3 × (−4), with m = 3 and r = −4, and x = 4 and y = 4:
• m = 0011, -m = 1101, r = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0
• Perform the loop four times:
• P = 0000 1100 0. The last two bits are 00.
• P = 0000 0110 0. Arithmetic right shift.
• P = 0000 0110 0. The last two bits are 00.
• P = 0000 0011 0. Arithmetic right shift.
• P = 0000 0011 0. The last two bits are 10.
• P = 1101 0011 0. P = P + S.
• P = 1110 1001 1. Arithmetic right shift.
• P = 1110 1001 1. The last two bits are 11.
• P = 1111 0100 1. Arithmetic right shift.
• The product is 1111 0100, which is −12.
https://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm
Two’s Complement – Multiplication and
Division
• Can perform multiplication and division by converting the
two’s complement numbers to their absolute values and
then negate the result if the signs of the operands are
different
• Most architectures implement more sophisticated
algorithms (Booth’s multiplication algorithm, Wallace tree,
Dadda multiplier)