Chapter 05 of 39

Binary Arithmetic & Overflow

In 1996 the first Ariane 5 rocket exploded about 40 seconds after launch. One of the causes was a number that did not fit: a 64-bit floating-point value was converted to a 16-bit signed integer, the value was too large, and the resulting error shut down the guidance system. Fixed-width arithmetic has limits, and hardware must detect when a result goes past them.

In this chapter we see how a processor adds and subtracts binary numbers, why 2's complement makes subtraction "just addition", how the end-around carry works in 1's complement, and, most importantly, how to detect overflow and tell it apart from carry. We also cover the status flags (N, Z, C, V), basic binary multiplication, and shift operations. Every example here uses 8-bit numbers unless stated, and every result was checked with a small simulator, including a brute-force test of all 65,536 pairs of 8-bit operands for the overflow rules.


Binary Addition

Binary addition works like decimal addition, column by column from the right, but a column "fills up" at 2 instead of 10.

a

b

carry in

sum bit

carry out

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

1

1

0

1

1

0

0

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

1

1

In words: 1 + 1 = 102 (write 0, carry 1), and 1 + 1 + 1 = 112 (write 1, carry 1). The circuit that does one column is a full adder; chaining n of them gives an n-bit adder (see Combinational Circuits: Adders, Multiplexers & Decoders).

Example: 45 + 30

carries  0111 1000
           0010 1101    (45)
         + 0001 1110    (30)
         -----------
           0100 1011    (75)     carry out of bit 7 = 0

The top row shows the carry coming into each column. Check: 64 + 8 + 2 + 1 = 75.


Binary Subtraction

Direct Subtraction with Borrows

On paper we can subtract column by column: 0 - 0 = 0, 1 - 0 = 1, 1 - 1 = 0, and 0 - 1 = 1 with a borrow from the next column (because 102 - 1 = 1).

borrows   1110
           1100    (12)
         - 0111    ( 7)
         ------
           0101    ( 5)

Hardware could have a separate subtractor, but there is a neater way.

Subtraction as Addition (2's Complement)

From Signed Numbers: Sign-Magnitude, 1's & 2's Complement, -B in 2's complement is ~B + 1 (invert and add 1). So:

A - B = A + (~B) + 1. Add the operands as unsigned bit patterns and discard any carry out of the MSB. The result is correct as long as it fits in n bits (no overflow).

The hardware needs just one adder. A control line M chooses the operation: each bit of B passes through an XOR gate with M (so B is inverted when M = 1), and M is also fed in as the carry into bit 0 (supplying the "+1").

   M = 0 : sum = A + B + 0        (addition)
   M = 1 : sum = A + ~B + 1       (subtraction)

   B(i) ---+
           XOR ----> adder input i          carry into bit 0 = M
   M ------+

Example: 45 - 30

30  = 0001 1110,   ~30 = 1110 0001

carries  1100 0011
           0010 1101    (45)
         + 1110 0001    (~30)
         +         1    (carry in = 1)
         -----------
         1 0000 1111    discard the carry out => 0000 1111 = 15

Example: -45 + 30

           1101 0011    (-45)
         + 0001 1110    (+30)
         -----------
           1111 0001    = -128 + 64 + 32 + 16 + 1 = -15     (no carry out)

We never needed to know which number was larger or what the signs were. That is the beauty of 2's complement.


1's Complement Addition: End-Around Carry

In 1's complement, -x is stored as (2n - 1) - x, which is 1 less than the 2's complement. So when a carry comes out of the MSB, the sum is 1 too small; the fix is to add the carry back into the LSB. This is called the end-around carry. These 4-bit examples show the rule:

(+5) + (-3):     0101
               + 1100        (-3 = invert 0011)
               ------
               1 0001        carry out = 1, add it back
               +    1
               ------
                 0010   = +2   correct

(-5) + (-2):     1010        (-5)
               + 1101        (-2)
               ------
               1 0111        add the carry back
                 1000   = -7  (invert -> 0111)  correct

(-3) + (+3):     1100
               + 0011
               ------
                 1111   = -0  (no carry; the "negative zero")

The end-around carry may ripple through the whole adder a second time, which is one reason 1's complement lost to 2's complement.

Sign-Magnitude Addition

For completeness: in sign-magnitude, if the signs are the same, add the magnitudes and keep the sign. If they differ, subtract the smaller magnitude from the larger and take the sign of the larger. This needs a magnitude comparator and a subtractor, so it is only used where it is unavoidable, such as the significands in floating-point hardware.


Overflow

Overflow occurs when the true result of an operation is outside the range that the destination's n bits can represent. The stored n-bit result is then wrong.

For 8-bit 2's complement the range is -128 to +127. So 100 + 50 = 150 must overflow:

carries  1100 0000
           0110 0100    (+100)
         + 0011 0010    (+50)
         -----------
           1001 0110    = -106  ??   two positives gave a negative => OVERFLOW

The hardware computed 150 correctly modulo 256, but 150 does not fit, so read as signed it wraps to 150 - 256 = -106. Overflow is the same wrap-around we saw on the number circle: going past +127 lands on -128.

When Can Overflow Happen?

  • Adding a positive and a negative number can never overflow: the result lies between the two operands, so it is in range.

  • Adding two numbers of the same sign can overflow.

  • For subtraction A - B, overflow is possible only when A and B have different signs (because A - B = A + (-B)).

Detection Rule 1: The Sign Rule

Overflow occurs in addition if and only if both operands have the same sign and the result has the opposite sign.

With operand sign bits an-1, bn-1 and result sign bit sn-1:

V = a'(n-1) . b'(n-1) . s(n-1)  +  a(n-1) . b(n-1) . s'(n-1)
    (two positives give a negative)  (two negatives give a positive)

Detection Rule 2: The Carry Rule

V = Cin XOR Cout of the MSB position: overflow occurs if and only if the carry into the sign bit differs from the carry out of the sign bit.

This is the rule hardware uses, since it needs just one XOR gate on two carries the adder already produces. Why it works: if both operands are positive (sign bits 0, 0), the carry out of the MSB is 0, and a carry into the MSB of 1 makes the sign bit 1, which is exactly a wrong (negative) result. If both are negative (1, 1), the carry out is 1, and a carry in of 0 makes the sign 0, a wrong (positive) result. For mixed signs, the carry in and out are always equal.

Worked Overflow Table

Operation

Bits

8-bit result

Carry into MSB

Carry out

V

Comment

45 + 30

00101101 + 00011110

01001011 (75)

0

0

0

Correct

100 + 50

01100100 + 00110010

10010110 (-106)

1

0

1

True sum 150 > 127

(-100) + (-50)

10011100 + 11001110

01101010 (+106)

0

1

1

True sum -150 < -128

45 + (-30)

00101101 + 11100010

00001111 (15)

1

1

0

Carry out 1 but correct

127 + 1

01111111 + 00000001

10000000 (-128)

1

0

1

Largest + 1 wraps to smallest

(-64) + (-64)

11000000 + 11000000

10000000 (-128)

1

1

0

-128 fits exactly

The last row is a favourite trick: there is a carry out, the result looks "big", yet there is no overflow because -128 is in range.


Carry vs Overflow

Students often treat these as the same. They are not. The adder does not know whether you mean the bits as signed or unsigned, so it reports both:

  • Carry (C) signals that an unsigned addition went out of range (result > 2n - 1).

  • Overflow (V) signals that a signed (2's complement) operation went out of range.

Bits added

Unsigned view

Signed view

C

V

00101101 + 00011110 = 01001011

45 + 30 = 75, correct

45 + 30 = 75, correct

0

0

11001000 + 01100100 = 00101100

200 + 100 = 44, wrong

-56 + 100 = 44, correct

1

0

01000110 + 01010000 = 10010110

70 + 80 = 150, correct

70 + 80 = -106, wrong

0

1

10011100 + 11001110 = 01101010

156 + 206 = 106, wrong

-100 + -50 = 106, wrong

1

1

All four combinations of C and V are possible. The program (via the compiler) decides which flag matters: for unsigned int it checks C, for int it checks V.


Status Flags (Condition Codes)

After an ALU operation, most processors record four facts about the result in a status register (called the flags register on x86 and NZCV on ARM):

Flag

Name

Set when

N (or S)

Negative / Sign

The MSB of the result is 1

Z

Zero

All bits of the result are 0

C

Carry

A carry came out of the MSB (unsigned overflow on addition)

V (or O)

Overflow

Signed overflow, V = carry into MSB XOR carry out of MSB

Branch instructions test these flags. A comparison CMP A, B simply computes A - B, throws the result away and keeps the flags. Then:

  • A = B if Z = 1.

  • Signed A < B if N XOR V = 1. (Checking N alone is wrong when the subtraction overflows: for A = -100, B = 50, the 8-bit result is +106 with N = 0, but V = 1, so N XOR V = 1 correctly says A < B.)

  • Unsigned A < B if the subtraction needed a borrow. Careful: processors disagree on how C reports it. x86 sets CF = 1 on a borrow. ARM computes A + ~B + 1 and leaves C as the adder's carry, so C = 1 means no borrow (A ≥ B).

We verified these three comparison rules for all 65,536 pairs of 8-bit operands.


Binary Multiplication

Multiplying in binary is easier than in decimal because each partial product is either 0 or a shifted copy of the multiplicand.

Example: 11 × 13 (unsigned, 4-bit operands)

            1011      (11, multiplicand)
          x 1101      (13, multiplier)
          ------
            1011      multiplier bit 0 = 1 -> copy
           0000       multiplier bit 1 = 0 -> zeros
          1011        multiplier bit 2 = 1 -> copy, shifted 2
         1011         multiplier bit 3 = 1 -> copy, shifted 3
        --------
        10001111      = 143

Two important facts:

  • An n-bit × n-bit product needs up to 2n bits. 11 × 13 = 143 needs 8 bits. That is why processors keep a double-width product (for example MIPS's HI and LO registers, or x86's EDX:EAX).

  • For signed numbers, the 2n-bit product is again in 2's complement: -3 × 5 = -15 is 11110001 in 8 bits. Simply multiplying the 4-bit patterns as unsigned (13 × 5 = 65) would give the wrong 8-bit answer.

Hardware implements this with repeated add-and-shift. The circuit, and Booth's algorithm for signed multiplication, are covered in Booth's Multiplication Algorithm; division is in Division: Restoring & Non-Restoring.


Shift Operations

Operation

What happens

Example on 10110100

Use

Logical shift left (LSL / SHL)

Bits move left, 0 enters at the right, MSB falls out (into C)

01101000

Multiply by 2

Logical shift right (LSR / SHR)

Bits move right, 0 enters at the left

01011010

Unsigned divide by 2

Arithmetic shift right (ASR / SAR)

Bits move right, the sign bit is copied into the MSB

11011010

Signed divide by 2 (rounding down)

Rotate left (ROL)

The bit leaving at the left re-enters at the right

01101001

Bit manipulation, hashing, crypto

Shift Left = Multiply by 2 (Until It Overflows)

Shifting left by k multiplies by 2k. For signed numbers, the result is wrong (overflow) if the sign bit changes:

11000000 (-64)  << 1 = 10000000 (-128)   correct
10100000 (-96)  << 1 = 01000000 (+64)    overflow: sign changed
01000000 (+64)  << 1 = 10000000 (-128)   overflow: sign changed

Compilers use shifts to multiply by constants: x × 10 = (x << 3) + (x << 1). For x = 13: 104 + 26 = 130.

Arithmetic Right Shift Rounds Down

Arithmetic right shift by 1 divides by 2 and rounds towards minus infinity: -20 (11101100) becomes -10 (11110110), and -5 (11111011) becomes 11111101 = -3. But in C, Java and most languages, integer division rounds towards zero, so -5 / 2 = -2. That is why a compiler cannot blindly replace x / 2 by x >> 1 for signed x; it adds a small correction for negative values.


Seeing It in C

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

int main(void) {
    /* 8-bit signed: the sum is computed as int, then stored back in 8 bits */
    int8_t a = 100, b = 50;
    int8_t s = (int8_t)(a + b);
    printf("int8_t : 100 + 50 = %d\n", s);

    /* 8-bit unsigned: wraps modulo 256 (well defined in C) */
    uint8_t u = 200, v = 100;
    uint8_t t = (uint8_t)(u + v);
    printf("uint8_t: 200 + 100 = %u\n", t);

    /* Detecting overflow safely with a GCC/Clang builtin */
    int r;
    if (__builtin_add_overflow(INT_MAX, 1, &r))
        printf("INT_MAX + 1 overflows (wrapped result would be %d)\n", r);

    /* Arithmetic right shift vs division for negative numbers */
    int x = -5;
    printf("-5 >> 1 = %d,  -5 / 2 = %d\n", x >> 1, x / 2);
    return 0;
}

Output (GCC on x86-64 Linux):

int8_t : 100 + 50 = -106
uint8_t: 200 + 100 = 44
INT_MAX + 1 overflows (wrapped result would be -2147483648)
-5 >> 1 = -3,  -5 / 2 = -2

Exactly the values we computed by hand. Two language details matter here. First, signed overflow in C is undefined behaviour: you must not write INT_MAX + 1 and expect a wrap, because the compiler is allowed to assume it never happens. Use unsigned types, wider types or __builtin_add_overflow instead. Second, right-shifting a negative signed value is implementation-defined in C; GCC uses an arithmetic shift, as shown.


Solved Problems

Problem 1 (GATE style)

Two 8-bit 2's complement numbers A7...A0 and B7...B0 are added to give S7...S0 with carry out Cout. Write a Boolean expression, using only the sign bits A7, B7 and S7, that sets the overflow indicator.

Answer: V = A7' B7' S7 + A7 B7 S7'. Overflow means the operands have the same sign and the sum's sign differs. Note that Cout alone is not an overflow indicator for signed numbers (see 45 + (-30), which has Cout = 1 and no overflow).

Problem 2

Which of these 8-bit 2's complement operations overflow? (a) 0x7F + 0x01 (b) 0x80 + 0xFF (c) 0xC0 + 0xC0 (d) 0x64 - 0xCE

(a) 127 + 1    = 128, out of range         => overflow (result 0x80 = -128)
(b) -128 + -1  = -129, out of range        => overflow (result 0x7F = +127)
(c) -64 + -64  = -128, in range            => no overflow (result 0xC0 + 0xC0 = 0x80)
(d) 100 - (-50) = 150, out of range        => overflow (result 0x96 = -106)

Problem 3

Compute 50 - 100 in 8 bits and give N, Z, C (x86 convention, C = borrow) and V.

  0011 0010    (50)
+ 1001 1011    (~100)
+         1
-----------
  1100 1110    = -50, no carry out of bit 7

N = 1   (MSB of the result is 1)
Z = 0   (result is not zero)
V = 0   (50 and 100 have the same sign, so 50 - 100 cannot overflow)
C       carry out = 0, i.e. a borrow occurred
        => x86 sets CF = 1 (CF means borrow);  ARM sets C = 0 (C means no borrow)

The borrow tells us that, as unsigned numbers, 50 < 100; N XOR V = 1 tells us that, as signed numbers, 50 < 100.

Problem 4

What is the smallest number of bits needed to store the sum of two 8-bit unsigned numbers without overflow? And the product?

Largest sum = 255 + 255 = 510 < 512 = 29: 9 bits. Largest product = 255 × 255 = 65025 < 65536 = 216: 16 bits. In general, adding needs one extra bit; multiplying needs double the bits.


Common Mistakes Students Make

  • Treating carry out as overflow for signed numbers. 45 + (-30) produces a carry out and a perfectly correct result.

  • Saying overflow is impossible when there is no carry. 100 + 50 has no carry out but overflows.

  • Forgetting the +1 in A + ~B + 1 (that would compute A - B - 1, the 1's complement way).

  • Checking "N = 1" for signed less-than. The correct test is N XOR V.

  • Assuming x >> 1 equals x / 2 for negative x. Shift rounds down; C division rounds towards zero.

  • Keeping only n bits of an n × n product. The full product needs 2n bits.

  • Relying on signed wrap-around in C. It is undefined behaviour; only unsigned arithmetic wraps by definition.


GATE / Interview Questions

1. Why can adding a positive and a negative number never overflow?

The result lies between the two operands (it is closer to zero than the larger magnitude), and both operands are already in range, so the result is in range too.

2. State the hardware rule for detecting 2's complement overflow.

Overflow = carry into the sign bit XOR carry out of the sign bit. Equivalently, the operands have the same sign and the result has the opposite sign.

3. In 4-bit 2's complement, compute 0111 + 0001 and state C and V.

Result 1000 (-8). Carry into MSB = 1, carry out = 0, so V = 1, C = 0. The true sum 8 exceeds the 4-bit maximum of 7.

4. Add (-5) and (-2) in 4-bit 1's complement.

1010 + 1101 = 1 0111. Add the end-around carry: 0111 + 1 = 1000, which is -7 in 1's complement. Correct.

5. What is the difference between logical and arithmetic right shift?

Logical shift right fills the vacated MSB with 0 (correct for unsigned division by 2). Arithmetic shift right copies the sign bit (correct for signed division by 2, rounding toward minus infinity).

6. Can the carry flag and the overflow flag both be 1 after an addition? Give an example.

Yes. 10011100 + 11001110 (-100 + -50 signed, or 156 + 206 unsigned) gives 01101010 with C = 1 and V = 1: wrong in both interpretations.

7. How would you detect overflow when adding two signed ints in C?

Check before adding: if b > 0 and a > INT_MAX - b, or b < 0 and a < INT_MIN - b, it would overflow. Or use __builtin_add_overflow(a, b, &r) in GCC/Clang, which typically compiles to an add followed by a test of the CPU's overflow flag.


Summary

  • Binary addition is column-wise with carries; one full adder per bit.

  • In 2's complement, A - B = A + ~B + 1; one adder with an XOR row and carry-in does both operations, and the carry out is discarded.

  • 1's complement addition needs an end-around carry and can produce -0.

  • Overflow: result outside the representable range. In 2's complement, possible only when adding numbers of the same sign; detected by V = Cin(MSB) XOR Cout(MSB) or by the sign rule.

  • C flags unsigned overflow, V flags signed overflow; all four combinations occur.

  • Flags N, Z, C, V drive comparisons: signed A < B is N XOR V; unsigned A < B is "borrow".

  • An n × n multiplication needs 2n bits. Shift left multiplies by 2; arithmetic shift right divides by 2 rounding down.

Integers cover only whole numbers in a limited range. To store values like 3.14, 6.022 × 1023 or 0.000001, computers use a scientific-notation format, which we study next in Floating-Point Representation (IEEE 754).