Adding, subtracting and multiplying in binary, two's complement, and how to spot overflow.
Adding in binary
Binary addition works just like the column addition you learned at school, with fewer facts to remember. When a column reaches two, write 0 and carry 1 into the next column.
Column adds up to
Write
Carry
0
0
0
1
1
0
2 (1 + 1)
0
1
3 (1 + 1 + carry)
1
1
> Loading the animation…
Worked example: 11 + 6
Add 1011 and 0110.
Rightmost column: 1 + 0 = 1, carry 0.
Next: 1 + 1 = 2, write 0, carry 1.
Next: 0 + 1 + 1 = 2, write 0, carry 1.
Next: 1 + 0 + 1 = 2, write 0, carry 1.
The last carry becomes a new leftmost digit.
Answer:10001, which is 17.
Four bits can only hold up to 15, so that sum needed a fifth bit. If the hardware has only four bits, it keeps 0001 and raises its carry out. For unsigned numbers, a carry out of the top bit means the result didn't fit. This is called overflow.
Subtracting and multiplying
Subtraction by hand works by borrowing: when a column would go below zero, borrow from the next column, which adds two here. For example, 1010 − 0011 = 0111, or 10 − 3 = 7. Later in this chapter you'll see that hardware avoids borrowing altogether.
Multiplication is easier than in decimal because each digit is 0 or 1. Every 1 in the multiplier adds a shifted copy of the top number, and every 0 adds nothing. This is called shift and add.
Worked example: 13 × 5
Multiply 1101 by 101.
The rightmost multiplier bit is 1: copy 1101.
The middle bit is 0: add nothing.
The left bit is 1: copy 1101 shifted two places, giving 110100.
Add them: 1101 + 110100 = 1000001.
Answer:1000001, which is 65.
TipShifting left by one place multiplies by 2, and shifting right by one place divides by 2 and drops the remainder. Hardware does this with wires, at no cost, so designers multiply by 2, 4 or 8 this way.
Negative numbers
Hardware has no minus sign, only bits, so negative numbers need an agreed coding. There have been three main ones. Here is how each writes −5 in 4 bits.
Method
How it makes a negative
+5
−5
4-bit range
Sign-magnitude
Top bit is the sign, the rest is the size
0101
1101
−7 to +7
1's complement
Invert every bit
0101
1010
−7 to +7
2's complement
Invert every bit, then add 1
0101
1011
−8 to +7
The first two have an awkward flaw: two different patterns mean zero (0000 and 1000 in sign-magnitude, 0000 and 1111 in 1's complement), and adding signed numbers needs special cases. Two's complement has one zero, and the plain binary adder works on it unchanged. Nearly every computer uses it.
The easiest way to read a two's complement number is to give the top bit a negative weight. In 4 bits the position values are −8, 4, 2, 1. So 1011 = −8 + 2 + 1 = −5.
n-bit two's complement range: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1
8 bits hold −128 to 127. There's one more negative value than positive, because 0 uses up one of the patterns with a 0 on top.
Worked example: Negating a number
What is −104 in 8-bit two's complement?
104 = 0110 1000.
Invert every bit: 1001 0111.
Add 1: 1001 1000.
Check with weights: −128 + 16 + 8 = −104.
Answer:1001 1000
TipA shortcut for negating: copy the bits from the right up to and including the first 1, then invert everything to its left. From 0110 1000, keep 1000 and invert 0110 to get 1001 1000.
To fit a number into more bits, copy its sign bit into the new positions. This is sign extension: 1011 and 1111 1011 are both −5, and 0101 and 0000 0101 are both +5.
Practice
What decimal value is the 8-bit two's complement number 1111 1011?
Subtracting by adding
This is why two's complement won: A − B = A + (invert B) + 1. One adder can do both jobs. An XOR gate on each B input passes the bit through when its control is 0 and inverts it when its control is 1, and the same control feeds the adder's carry in to provide the + 1.
> Loading the circuit…
A 4-bit adder/subtractor. With sub off it adds. With sub on, each bit of b is inverted and the carry in is 1, so it subtracts. The displays are in hex.
Set a = 9, b = 3 and turn sub on. The result is 6.
Now try a = 3, b = 9. The result is A, or 1010, which is −6 in two's complement.
Notice the carry light. When subtracting, a carry of 1 means there was no borrow.
Worked example: 6 − 3 in 4 bits
Compute 0110 − 0011 by adding.
−3 is the two's complement of 0011, which is 1101.
Add: 0110 + 1101 = 1 0011.
Drop the carry out of the top bit, as the hardware does.
Answer:0011, which is 3.
Signed overflow
Overflow means the true answer doesn't fit in the bits you have. For signed numbers it isn't the same thing as a carry out, as the last example shows: it had a carry out and a correct answer.
The signs tell you. Adding a positive and a negative can never overflow, because the result lies between them. Adding two numbers of the same sign overflows if the result has the opposite sign.
Sum
True answer
Result in 4 bits
Overflow?
0111 + 0001
7 + 1 = 8
1000 = −8
Yes: two positives gave a negative
1000 + 1111
−8 + −1 = −9
0111 = +7
Yes: two negatives gave a positive
0110 + 1101
6 + −3 = 3
0011 = +3
No: the signs differ
> Loading the animation…
Hardware uses an equivalent rule that takes a single gate:
overflow = carry into the top bit ⊕ carry out of the top bit
Practice
In 8-bit two's complement, what does 100 + 50 give?
Watch outAdding unsigned and adding signed use the same bits and the same adder. What differs is how you read the result and which flag you check: carry out for unsigned, overflow for signed.
Complements in any baseGATE: fine to skip at first
Complements work in every base. For a number N with n digits in base r, the r's complement is rⁿ − N and the (r−1)'s complement is rⁿ − 1 − N. In base 2 those are the 2's and 1's complements, and in base 10 the 10's and 9's complements.
Worked example: Decimal complements
Find the 9's and 10's complements of 2357.
9's complement: subtract each digit from 9, which gives 7642.
10's complement: add 1, which gives 7643.
Answer:7642 and 7643.
In 1's complement arithmetic, a carry out of the top bit has to be added back into the bottom. This is called end-around carry. To compute 6 − 3 in 4 bits, add 0110 + 1100 to get 1 0010, then add the carry back in to get 0011 = 3. Two's complement needs no such step, and that's one reason it won.
Practice · GATE-style
What is the decimal value of the 6-bit two's complement number 101100?