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.

One Step Past the Top
27
26
25
24
23
22
21
20

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

27
26
25
24
23
22
21
20

Result: 10000000 (-128 signed)

Carry 0 Overflow 1

Two positives gave a negative.

  1. 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.
  2. 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 bitCarry out
0, 0, 000
one 1 among them10
two 1s among them01
1, 1, 111

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.

Carries From Right to Left
23
22
21
20

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

23
22
21
20

Result: 1000 (-8 signed)

Carry 0 Overflow 1

Two positives gave a negative.

  1. 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.
  2. 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.

A Minus B on the Adder
23
22
21
20

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

23
22
21
20

Result: 0010 (2 signed)

Carry 1 Borrow 0 (carry means no borrow) Overflow 0

The signed result fits in this width.

  1. 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".
  2. 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 addedUnsignedSignedCarry outCarry into bit 7Overflow
100 + 27127100 + 27 = 127000
127 + 1128127 + 1 = -128011
200 + 10044-56 + 100 = 44110
128 + 255127-128 + -1 = 127101

Measured on the simulator. Red marks a reading that is wrong; all four combinations of the two flags occur.

One Adder, Two AlarmsArrows show signals. The adder is the same for both readings; only the alarm you look at changes.
  • I/O
  • Datapath
  • Data
One adder, two alarmsArrows show signals. The adder is the same for both readings; only the alarm you look at changes. io a, b two N-bit patterns datapath Adder N columns with carries io sum N bits io Carry out unsigned result toolarge io Overflow signed result out ofrange operandssum bitscarry out of the topbitcarry in XOR carryout of the top bit
  1. datapath AdderN columns with carries
    • sum bits → sum
    • carry out of the top bit → Carry out
    • carry in XOR carry out of the top bit → Overflow
  2. io Carry outunsigned result too large
  3. io Overflowsigned result out of range
  4. io a, btwo N-bit patterns
    • operands → Adder
  5. io sumN bits
  1. Unsigned numbers

    Look at the carry out of the top bit. A 1 means the true sum needed one more bit.

  2. Signed numbers

    Look at overflow. It is 1 when the carry into the top bit differs from the carry out of it.

  3. 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.

Adding 40 per Step in a Signed ByteTwo accumulators add 40 in every step. One wraps and one saturates at +127.
01234567step01234567wrap04080120-96-56-1624sat04080120127120 + 40 does not fit
Scroll horizontally ↔
  1. Cycle 3

    Both accumulators hold 120. One more step would be 160, above the largest signed byte.

  2. Cycle 4

    The wrapping one jumps to -96: it kept the low eight bits of 160. The saturating one stops at 127.

  3. 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
  1. 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.

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: a=01111111 b=00000001 sum=10000000 unsigned: 127 + 1 = 128 carry=0 signed: 127 + 1 = -128 overflow=1

Check Yourself

Predict the outputThe three variables are unsigned bytes. What exact line does the program print?
module tb;
  logic [7:0] a, b, sum;
  initial begin
    a = 8'd200;
    b = 8'd100;
    sum = a + b;
    $display("%0d", sum);
  end
endmodule
Spot the bugEach option sets v, the signed-overflow flag of a 4-bit add. c4 is the carry out of the top bit and c3 is the carry into it. The bench tries all 256 pairs. Which option fails?
Read the waveformAn unsigned byte counts up by 100 per step and wraps. In which step does it first show a value below the one before?
Adding 100 per step in an unsigned byte
01234step01234count010020044144
Scroll horizontally ↔

One add per step. Measured on the simulator.

ConceptA saturating adder for signed bytes adds 100 and 100. What is its output?
ConceptAn adder computes a - b as a + ~b + 1 on unsigned bytes. What does a carry out of 0 mean?

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.

Before
overflow = carry;
After
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;.

Before
sum = a + b;            // carry lost
After
{carry, sum} = a + b;   // carry kept

Wrong 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 - b is a + ~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.

Practice

Report a problem with this page