Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 67 ยท Data Representation

Binary Arithmetic and Overflow

Learn how hardware adds, subtracts and multiplies binary numbers, what the carry and overflow flags mean, and how shifts replace multiplication.

A processor does not know what a number "means". It only has circuits that combine bit patterns. Addition, subtraction and multiplication are the same few ideas you learned in primary school, applied to base 2, with one big difference: the result has to fit in a fixed number of bits. When it does not fit, the hardware raises flags, and software that ignores them produces bugs, crashes and security holes.

In this lesson you will add and subtract binary numbers by hand, learn the difference between the carry flag and the overflow flag, see how multiplication reduces to shifts and adds, and build a small 8-bit ALU model in Python. It assumes you know two's complement and number systems.

Adding binary numbers

Binary addition has only four single-column cases:

a b sum bit carry out
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

With an incoming carry, 1 + 1 + 1 gives sum bit 1 and carry out 1. You work from the right-most column to the left, passing the carry along:

TEXT
    1 1 1 0     carries
      0 1 1 0   6
    + 0 1 1 1   7
    ---------
      1 1 0 1   13

In hardware, a chain of one-bit adders does exactly this. You will build one in Combinational Circuits.

Fixed width and the carry flag

A real register has a fixed width, say 8 bits. If you add 200 + 100 as unsigned numbers, the true answer 300 needs 9 bits. The ninth bit does not fit in the register, so it is thrown away and the stored result is 300 - 256 = 44. The CPU does not discard that bit silently: it saves it in the carry flag (C).

flowchart LR
  A["8-bit a"] --> ADD(("+"))
  B["8-bit b"] --> ADD
  ADD --> R["8-bit result"]
  ADD --> C["Carry flag"]

An 8-bit adder produces an 8-bit result and a carry-out bit.

For unsigned numbers, carry = 1 after an addition means the answer wrapped around and is wrong. This is also how multi-word arithmetic works: to add two 64-bit numbers on a 32-bit machine you add the low halves, then add the high halves plus the saved carry.

Subtraction is addition

Hardware rarely has a separate subtractor. Since a - b = a + (-b) and in two's complement -b = ~b + 1, subtraction is addition with the second operand inverted and a carry-in of 1:

TEXT
a - b  =  a + (~b) + 1

The same adder does both jobs. A control signal chooses whether b passes through an inverting gate and whether the carry-in is 0 or 1. You will see this in Building an ALU.

A detail that surprises people: on many CPUs (ARM, for example) the carry flag after a subtraction means no borrow, so it is 1 when a >= b for unsigned numbers. On x86 the same flag means borrow and is the opposite. The arithmetic is identical; only the flag's polarity differs. Always read your CPU's manual before testing carry after a subtract.

Overflow is not carry

Carry tells you about unsigned overflow. The overflow flag (V) tells you about signed overflow, where the result of adding two numbers does not fit in the signed range (-128 to 127 for 8 bits).

Signed overflow can happen only when you add two numbers of the same sign and the result has the opposite sign:

  • 100 + 50 = 150 does not fit in a signed byte. The bits give -106. Two positives made a negative.
  • -100 + -50 = -150 wraps to +106. Two negatives made a positive.
  • Adding a positive and a negative can never overflow, because the result lies between the two operands.

Hardware computes V cheaply: it is true when the carry into the sign bit differs from the carry out of the sign bit. Equivalent software test: the operands have the same sign bit, and the result's sign bit is different.

The two flags are independent. All four combinations occur:

Example (8-bit) Unsigned view Signed view C V
0x50 + 0x50 80 + 80 = 160, fits 80 + 80 = 160, no fit 0 1
0xF0 + 0xF0 240 + 240 = 480, no fit -16 + -16 = -32, fits 1 0
0xFF + 0x01 255 + 1 = 256, no fit -1 + 1 = 0, fits 1 0
0x80 + 0x80 128 + 128 = 256, no fit -128 + -128, no fit 1 1

The CPU does not know whether your bytes are signed or unsigned. It sets both flags every time, and the program (or the compiler) decides which one to look at.

An 8-bit ALU model

Python integers never overflow, so to model hardware we mask results to 8 bits and compute the flags ourselves.

Python Add and subtract with flags

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Run it and look at the last three lines. 5 - 3 gives carry 1 (our model, like ARM, reports "no borrow"). 3 - 5 gives carry 0, which means a borrow happened for unsigned numbers; the signed answer is -2. And 0x80 - 1 (that is -128 - 1) sets V, because -129 does not fit in a signed byte.

The overflow test ((a ^ result) & (b ^ result) & SIGN) reads: "both operands have a sign different from the result's sign". That is the same-signs-in, different-sign-out rule in one expression.

Multiplication

Binary multiplication is long multiplication with a pleasant simplification: each digit of the multiplier is 0 or 1, so each partial product is either zero or a shifted copy of the multiplicand.

TEXT
      1 0 1 1    11
    x 0 1 1 0     6
    ---------
      0 0 0 0
    1 0 1 1        (shifted 1)
  1 0 1 1          (shifted 2)
0 0 0 0
---------------
  1 0 0 0 0 1 0    66

An n-bit times n-bit product needs up to 2n bits. That is why x86 mul puts the result in two registers, and why C's int * int can overflow even when both operands are legitimate.

The classic shift-and-add algorithm does this with a loop: for each bit of the multiplier, from the lowest, add the (shifted) multiplicand if the bit is 1.

Python Shift-and-add multiplication

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The full product of 255 x 255 is 65025, which needs 16 bits. Keep only the low 8 bits and you get a result that looks plausible and is completely wrong. Real processors offer both a "low half" multiply and a "full" multiply for this reason.

Signed multiplication is trickier because simply shifting and adding breaks for negative multiplicands. Hardware uses sign-extended partial products or Booth's algorithm, which recodes runs of 1s in the multiplier to reduce the number of additions. The key fact for programmers: for the low n bits of the result, signed and unsigned multiplication give identical bits. Only the high half differs.

Shift tricks

Shifting a binary number left by one bit doubles it; shifting right halves it. This is the same as moving the decimal point in base 10.

  • x << k multiplies by 2**k (until bits fall off the left edge).
  • x >> k on an unsigned value divides by 2**k, rounding down.
  • On a signed value you need an arithmetic right shift, which copies the sign bit into the vacated positions. A logical right shift would turn -8 into a large positive number.
  • x & (2**k - 1) is x mod 2**k, a very cheap remainder.

Compilers use these identities constantly. x * 10 becomes (x << 3) + (x << 1), and x / 8 for unsigned x becomes a single shift.

Python Shifts, masks and arithmetic right shift

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note the last line: an arithmetic right shift rounds toward minus infinity, so -7 >> 1 is -4, not -3. Many languages' integer division rounds toward zero instead (C gives -7 / 2 == -3), which is why compilers add a small correction before shifting signed values.

Python has no fixed-width integers, so use & MASK after every operation when you want hardware behavior. See Python's bitwise operators for the full operator list.

Overflow in the real world

Overflow bugs are not academic. A 32-bit signed counter that reaches 2,147,483,647 and increments becomes -2,147,483,648. Software has misjudged array sizes, computed negative prices, and opened security holes this way: size = count * element_size wraps around to a small number, a small buffer is allocated, and a large copy then overruns it.

Hardware and languages respond differently:

  • Wrap around: x86, ARM and most languages' unsigned types just keep the low bits.
  • Trap: some architectures can raise an exception on overflow, and some languages check (Python integers grow instead; Rust panics in debug builds).
  • Saturate: DSP and graphics instructions clamp to the maximum or minimum value, which is often better for audio and pixels.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In an 8-bit adder, what does the carry flag tell you after adding two unsigned numbers?

    A carry out of the top bit means the real sum needed a ninth bit, so the stored 8-bit result is wrong as an unsigned number.
  2. 2. Which addition can set the overflow flag (signed overflow)?

    Signed overflow needs operands with the same sign and a result with the opposite sign. Mixed signs can never overflow.
  3. 3. How does hardware usually compute a - b with an adder?

    Inverting b and adding a carry-in of 1 produces -b in two's complement, so the same adder handles both operations.
  4. 4. How many bits can the product of two 8-bit numbers need?

    An n-bit by n-bit product can need up to 2n bits. 255 x 255 = 65025 needs 16 bits.
  5. 5. Why is an arithmetic right shift needed for signed values?

    A logical right shift fills with zeros, turning a negative number into a large positive one. An arithmetic shift fills with the sign bit.

Summary

  • Binary addition works column by column with a carry; subtraction is a + ~b + 1 on the same adder.
  • Fixed-width results wrap around. The carry flag reports unsigned overflow; the overflow flag reports signed overflow, and they are independent.
  • Overflow occurs when two same-sign operands give a result of the opposite sign.
  • Multiplication is shift-and-add, and an n-bit product may need 2n bits.
  • Left shifts multiply by powers of two, right shifts divide, and masks give remainders; signed values need arithmetic right shifts.
  • Hardware may wrap, trap or saturate on overflow, and ignoring it causes real bugs.

Next, move from integers to fractions with Floating-Point Numbers and IEEE 754.