Fixed-point arithmetic and overflow

Why it exists

A computer adds numbers in registers of a fixed width, say 8, 32 or 64 bits. The mathematical sum of two $n$-bit numbers may need $n+1$ bits. When that happens, the hardware cannot raise an exception on its own: it keeps the low $n$ bits and sets flags that describe what happened. The same adder circuit is used for unsigned and for signed (2's complement) numbers, so the flags are the only way software can tell whether the answer is meaningful. Almost every GATE question in this area asks one of three things: what is the result in $n$ bits, did it overflow (and which kind), or what are the flag values.

Prerequisites

You need the 2's complement system from signed number representation: ranges, negation, and the fact that $-x \equiv 2^n - x$.

Precise definitions

Fixed-width (modular) arithmetic. An $n$-bit adder computes $(A + B) \bmod 2^n$ and a carry bit. The same output bits are the correct result for unsigned operands and for 2's complement operands, provided the true result is within the range of the interpretation.

The four flags. After an addition (or a subtraction, which is addition of the complement) of two $n$-bit words $A$ and $B$ giving the $n$-bit result $S$:

• C (carry): the carry out of the most significant bit.
• V (overflow): set when the signed result is outside the 2's complement range.
• N (negative): the sign bit of $S$.
• Z (zero): set when all bits of $S$ are 0.

Unsigned overflow happens exactly when $C = 1$ for an addition: the true sum is at least $2^n$.

Signed overflow for addition happens exactly when $V = 1$. Three equivalent tests:

1. The two operands have the same sign and the result has the opposite sign. (Operands of different sign can never overflow when added.)
2. The carry into the sign bit differs from the carry out of the sign bit: $V = c_{n-1} \oplus c_n$.
3. The true sum is outside $-2^{n-1}\dots 2^{n-1}-1$.

For subtraction $A - B$ computed as $A + \bar{B} + 1$: overflow happens when $A$ and $B$ have different signs and the sign of the result differs from the sign of $A$.

Carry and borrow in subtraction. Subtraction is done as $A + \overline{B} + 1$. The carry out of this addition is 1 exactly when $A \ge B$ as unsigned numbers, that is, when there is no borrow. So "carry = NOT borrow". Some processors (ARM) keep this carry as C after a subtraction; others (x86) invert it so that the flag means borrow. A GATE question that asks about the flag will state its convention or the machine.

Comparison from the flags (after computing $A - B$):

The signed tests use $N \oplus V$ rather than $N$ alone because after an overflow the sign bit of the wrapped result is wrong; $V$ corrects it.

Width rules.

• The sum of two $n$-bit numbers needs at most $n + 1$ bits. The sum of $k$ unsigned $n$-bit numbers needs at most $n + \lceil \log_2 k \rceil$ bits.
• The product of two $n$-bit numbers (signed or unsigned) fits in $2n$ bits. The only product that needs the very top of the signed range is $(-2^{n-1})^2 = 2^{2n-2}$, which still fits.
• Extra (guard) bits above the operands stop overflow in a long chain of additions.

Fixed-point fractions (Q formats). A fixed-point number stores an integer $R$ and agrees in advance that there are $f$ bits after the binary point: the value is $R / 2^f$. Written $Qm.f$ for $m$ integer bits and $f$ fraction bits ($m$ includes the sign bit for signed formats). The resolution (distance between neighbouring values) is $2^{-f}$. Unsigned $Qm.f$ covers $0$ to $2^m - 2^{-f}$; signed covers $-2^{m-1}$ to $2^{m-1} - 2^{-f}$. Addition and subtraction of numbers with the same format is just integer addition on the raw values. Multiplication of $Qm.f$ by $Qm.f$ gives a raw product with $2f$ fraction bits ($Q2m.2f$); shift right by $f$ to return to $Qm.f$, which may overflow.

How it works

Step through six additions of 8-bit numbers. Each shows the operands, the wrapped sum, the carry out of the sign bit, the carry into it, and the overflow flag $V$ computed as their exclusive-or. The test file recomputes every value separately.

  01100100  (100)
+ 00110010  (50)
= 10010110  carry out 0, carry into sign bit 1

The key fact to see in the animation is that carry and overflow are independent. All four combinations occur: ($-3 + 5$) has a carry and no overflow, ($100 + 50$) has overflow and no carry, ($-100 + -50$) has both, and ($1 + 2$) has neither. The carry tells you about the unsigned interpretation, the overflow tells you about the signed one, and the same wrapped bit pattern is the result in both.

Worked examples

#include <stdio.h>
#include <stdint.h>
 
/* 8-bit add: returns the wrapped sum and sets the flags the way a CPU does */
static uint8_t add8(uint8_t a, uint8_t b, int *c, int *v, int *n, int *z) {
    unsigned wide = (unsigned)a + b;
    uint8_t s = (uint8_t)wide;
    *c = (int)(wide >> 8);
    *v = (int)((~(a ^ b) & (a ^ s)) >> 7 & 1);
    *n = s >> 7;
    *z = (s == 0);
    return s;
}
 
static void show(int x, int y) {
    int c, v, n, z;
    uint8_t s = add8((uint8_t)x, (uint8_t)y, &c, &v, &n, &z);
    printf("%4d + %4d = %02X  C=%d V=%d N=%d Z=%d\n", x, y, s, c, v, n, z);
}
 
int main(void) {
    show(100, 50);
    show(-100, -50);
    show(-3, 5);
    show(127, 1);
    show(-1, 1);
    int c, v, n, z;
    uint8_t d = add8(5, (uint8_t)(~7u + 1), &c, &v, &n, &z);
    printf("5 - 7: %02X (%d) carry=%d borrow=%d\n", d, (int8_t)d, c, !c);
    d = add8((uint8_t)-100, (uint8_t)(~100u + 1), &c, &v, &n, &z);
    printf("-100 - 100: %02X N=%d V=%d N xor V=%d\n", d, n, v, n ^ v);
    unsigned q = 0x58, r = 0x30;
    unsigned p = q * r;
    printf("Q4.4: %.4f * %.4f = %.4f, raw %X, rescaled %X\n", q / 16.0, r / 16.0, p / 256.0, p, p >> 4);
    return 0;
}

 100 +   50 = 96  C=0 V=1 N=1 Z=0
-100 +  -50 = 6A  C=1 V=1 N=0 Z=0
  -3 +    5 = 02  C=1 V=0 N=0 Z=0
 127 +    1 = 80  C=0 V=1 N=1 Z=0
  -1 +    1 = 00  C=1 V=0 N=0 Z=1
5 - 7: FE (-2) carry=0 borrow=1
-100 - 100: 38 N=0 V=1 N xor V=1
Q4.4: 5.5000 * 3.0000 = 16.5000, raw 1080, rescaled 108

Cheat box

Traps and GATE patterns

Connections

The adder that produces these flags is built from full adders in adders and subtractors, and the ALU in ALU design exposes them to the program. Booth multiplication computes the $2n$-bit product of signed numbers. Floating point avoids this choice of a fixed point position at the price of rounding, see IEEE 754.

PYQs

Consider the unsigned 8-bit fixed point binary
Number System below:

b7b6b5b4b3b2b1b0

where the position of the binary point is between
b3 and b2. Assume b7 is the most significant bit
(MSB). Some of the decimal numbers listed below
cannot be represented exactly in the above
representation:

 (i) 31.500 (ii) 0.875 (iii) 12.100 (iv) 3.001

Which one of the following statements is true?

Self-check

Revision card

References