Addition, Subtraction and Overflow
Add and subtract two's-complement numbers by hand, tell a carry from a signed overflow, and choose between wrapping and saturating.
You Will Be Able To
- Add two binary numbers column by column with carries.
- Subtract by adding the inverted operand plus one.
- Decide from the carry and the signs if a result fits, unsigned and signed.
- Clamp a result at the end of its range in place of letting it wrap.
- Lesson
- G1.3
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A heater stores its setpoint in a signed byte. At 127 the user presses "up" once more. The setpoint becomes -128 and the heater turns off. No error was raised: the adder gave the only answer that eight wires can carry.
Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.
- Unsigned
- 127
- Two’s complement
- 127
Carry chain (out → in): 0 1 1 1 1 1 1 1 0
Add operand B
Result: 10000000 (-128 signed)
Carry 0 Overflow 1
Two positives gave a negative.
- 127 + 1. The carries run through every column. The result pattern is 10000000. Unsigned, that is 128. Signed, it is -128, and the overflow flag is set.
- 100 + 27. This sum is 127 in both readings. No carry out and no overflow.
Click any bit of either operand. The carry row, the result and both flags update.
Adding Column by Column
Binary addition works like decimal addition, with only two digits. Start at the LSB. Add the two bits and the carry from the column on the right. Write the low bit of that small sum and carry the high bit to the left.
| Bits to add (a, b, carry in) | Sum bit | Carry out |
|---|---|---|
| 0, 0, 0 | 0 | 0 |
| one 1 among them | 1 | 0 |
| two 1s among them | 0 | 1 |
| 1, 1, 1 | 1 | 1 |
The rule for one column: count the 1s. The sum bit is the low bit of that count and the carry is the high bit.
Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.
- Unsigned
- 5
- Two’s complement
- 5
Carry chain (out → in): 0 1 1 1 0
Add operand B
Result: 1000 (-8 signed)
Carry 0 Overflow 1
Two positives gave a negative.
- 5 + 3. Bit 0: 1 + 1 is 10, so write 0 and carry 1. Bit 1: 0 + 1 + 1 is 10 again. Bit 2: 1 + 0 + 1 is 10. Bit 3: only the carry, so write 1. The result is 1000.
- Two readings of one result. Unsigned, 1000 is 8, which is right. Signed, it is -8: two positive numbers gave a negative one. The overflow flag says so.
The same four wires give 8 or -8. Which one is right depends on how the operands were meant.
One adder serves both readings. That is the reason hardware uses two's complement.
Subtraction Is Addition
To subtract b, add its negative. Lesson G1.2 showed that the negative is "invert and add one". So a - b is a + ~b + 1. The extra one enters the adder as a carry into bit 0.
Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.
- Unsigned
- 5
- Two’s complement
- 5
Carry chain (out → in): 1 1 0 1 1
Subtract operand B
Result: 0010 (2 signed)
Carry 1 Borrow 0 (carry means no borrow) Overflow 0
The signed result fits in this width.
- 5 - 3. The adder sees 0101 + 1100 + 1. The result is 0010 with a carry out of 1. Here a carry of 1 means "no borrow".
- 3 - 5. The adder sees 0011 + 1010 + 1. The result is 1110, which is -2, and the carry out is 0. A carry of 0 means the unsigned subtraction needed a borrow.
In a subtraction the carry out is inverted: 1 for no borrow and 0 for a borrow.
Carry and Overflow Are Two Alarms
A result may not fit. The carry out of the top bit says that an unsigned result did not fit. Overflow says that a signed result did not fit. They are different tests, and each can be set without the other.
| Bytes added | Unsigned | Signed | Carry out | Carry into bit 7 | Overflow |
|---|---|---|---|---|---|
| 100 + 27 | 127 | 100 + 27 = 127 | 0 | 0 | 0 |
| 127 + 1 | 128 | 127 + 1 = -128 | 0 | 1 | 1 |
| 200 + 100 | 44 | -56 + 100 = 44 | 1 | 1 | 0 |
| 128 + 255 | 127 | -128 + -1 = 127 | 1 | 0 | 1 |
Measured on the simulator. Red marks a reading that is wrong; all four combinations of the two flags occur.
- I/O
- Datapath
- Data
- Unsigned numbers
Look at the carry out of the top bit. A 1 means the true sum needed one more bit.
- Signed numbers
Look at overflow. It is 1 when the carry into the top bit differs from the carry out of it.
- The sum bits
The sum bits are the same in both cases. The flags only tell you how far to trust them.
Read the diagram as text
- a, b: two N-bit patterns
- Adder: N columns with carries
- sum: N bits
- Carry out: unsigned result too large
- Overflow: signed result out of range
- a, b → Adder: operands
- Adder → sum: sum bits
- Adder → Carry out: carry out of the top bit
- Adder → Overflow: carry in XOR carry out of the top bit
The table above shows the XOR rule on every row: overflow is 1 where the two carry columns differ.
There is a second way to see overflow. Adding a positive and a negative number can never overflow. Two operands with the same sign overflow when the result has the other sign.
Wrap or Saturate
When a result does not fit, plain hardware wraps around: it keeps the low bits. A counter may want that. A volume, a brightness or a filter output does not. Those use saturation: the result stops at the end of the range.
- Cycle 3
Both accumulators hold 120. One more step would be 160, above the largest signed byte.
- Cycle 4
The wrapping one jumps to -96: it kept the low eight bits of 160. The saturating one stops at 127.
- Cycle 7
The wrapping value climbs back through zero. The saturating value stays at the top.
Measured on the simulator. A wrapped value is far from the true one; a saturated value is as close as the range allows.
Wrapping add
logic signed [7:0] a, b, y;
assign y = a + b;
Measured: 120 + 40 gives -96.
Saturating add
logic signed [7:0] a, b, y;
logic signed [8:0] wide;
assign wide = a + b;
assign y = (wide > 127) ? 8'sd127 :
(wide < -128) ? -8'sd128 : wide[7:0];
Measured: 120 + 40 gives 127.
The saturating adder first forms the sum with one extra bit, so the true value is never lost. Then it clamps. A negative overflow clamps to -128, the other end.
Asked in interviews
What is the difference between carry and overflow?
Carry out of the top bit means an unsigned result did not fit. Overflow means a signed result did not fit. 127 + 1 in a byte sets overflow only. 255 + 1 sets carry only.
How do you detect signed overflow in an adder?
XOR the carry into the top bit with the carry out of it. The same test from outside: both operands have one sign and the sum has the other.
How does an adder subtract?
It adds the inverted second operand with a carry in of 1. That is two's-complement negation folded into the adder. The carry out then means "no borrow".
Try It
The sum pattern is 10000000. As an unsigned number it is 128, which is right, and the carry is 0. As a signed number it is -128, which is wrong, and the overflow flag is 1.
Change the operands to 8'd200 and 8'd100. Now the unsigned line is wrong (44, with carry 1) and the signed line is right: -56 + 100 is 44.
Try 8'd128 and 8'd255 to set both flags, and 8'd100 and 8'd27 to set neither.
a=01111111 b=00000001 sum=10000000 unsigned: 127 + 1 = 128 carry=0 signed: 127 + 1 = -128 overflow=1Check Yourself
Common Mistakes
Wrong Use the carry out as the signed overflow flag.
The carry tests the unsigned range; -56 + 100 gives a carry and a correct signed sum.
Fix For signed numbers, test the signs: the same sign in and a different sign out.
overflow = carry;overflow = (a[7] == b[7]) &&
(sum[7] != a[7]);Wrong Expect the hardware to stop or report an error when a sum does not fit.
An adder has a fixed number of output wires, so the extra bit is dropped without any signal.
Fix Compute the carry or the overflow flag yourself and decide what to do with it.
Wrong Assign a sum to a variable as wide as the operands and then look for the carry.
The ninth bit has nowhere to go and is lost.
Fix Make the left side one bit wider: {carry, sum} = a + b;.
sum = a + b; // carry lost{carry, sum} = a + b; // carry keptWrong Saturate a signed adder when its carry out is 1.
Two small negative numbers always give a carry, so correct sums would be clamped.
Fix Saturate on signed overflow, towards the sign of the operands.
Remember
- Add column by column from the LSB; the carry of each column joins the next one.
a - bisa + ~b + 1: one adder both adds and subtracts.- Carry out is the unsigned alarm. Overflow is the signed alarm: carry in XOR carry out of the top bit.
- Overflow needs two operands of the same sign and a result of the other sign.
- Hardware wraps unless you build saturation: form the sum one bit wider, then clamp.