Two's Complement, in depth: modular arithmetic, negation, carry versus overflow, sign extension and the INT_MIN traps

Integers modulo 2^n

An n-bit register holds one of 2^n bit patterns. Hardware addition on those patterns is addition modulo 2^n: add, then drop the carry out of the top bit. Unsigned interpretation reads pattern k as the number k, from 0 to 2^n - 1. Two's complement keeps the same patterns and the same adder, and reads every pattern with the top bit set as k - 2^n. With n = 8, pattern 11111111 is 255 unsigned and 255 - 256 = -1 signed.

Formally, the value of bits b_n-1...b₀ is -b_n-1·2^n-1 + Σ b_i·2ⁱ for i < n-1. The top bit carries a negative weight. It is not a separate sign flag. That is why one adder serves both interpretations: the two readings of any pattern differ by exactly 2^n, which is 0 modulo 2^n, so any sum computed modulo 2^n is right under both readings, as long as the true result fits.

Negation and the asymmetric range

Why is negation "invert the bits and add one"? Adding x to its bitwise complement ~x sets every bit, so x + ~x = 2^n - 1. Rearranging gives -x ≡ ~x + 1 (mod 2^n). Two other identities follow, and they appear all over bit-twiddling code: ~x = -x - 1 and -x = ~(x - 1). Python makes the first one visible, because ~5 prints -6.

There are 2^(n-1) negative patterns and 2^(n-1) non-negative ones, and zero takes one of the non-negative slots. So the range is -2^(n-1) to 2^(n-1) - 1, one more negative than positive. For 32 bits that is -2,147,483,648 to 2,147,483,647. The most negative value, INT_MIN, is its own negation: ~INT_MIN + 1 = INT_MAX + 1, which wraps back to INT_MIN. Many of the bugs at the end of this article start from this asymmetry. In exchange, two's complement has a single zero. Sign-magnitude and ones' complement both have a +0 and a -0, and both need extra adder logic. That is why both disappeared from general-purpose hardware.

Addition, carry and overflow

Since the bits come out the same either way, the only question is whether the true result fitted. The answer differs by reading. In unsigned arithmetic, the sum overflowed when a carry left the top bit: the C flag on x86 and Arm. In signed arithmetic, it overflowed when two operands of the same sign produced a result of the other sign: the V or OF flag. Adding two numbers of different signs can never overflow. A simulation makes the rules concrete and gives you an oracle for tests:

def to_signed(x, n):
    x &= (1 << n) - 1
    return x - (1 << n) if x >> (n - 1) else x

def add_n(a, b, n):
    mask = (1 << n) - 1
    ua, ub = a & mask, b & mask
    total = ua + ub
    r = total & mask
    carry = total >> n                      # unsigned overflow
    sa, sb, sr = ua >> (n - 1), ub >> (n - 1), r >> (n - 1)
    overflow = sa == sb and sr != sa        # signed overflow
    return to_signed(r, n), carry, overflow

print(add_n(100, 27, 8))    # (127, 0, False)
print(add_n(100, 28, 8))    # (-128, 0, True)   signed overflow, no carry
print(add_n(-1, 1, 8))      # (0, 1, False)     carry, but signed result is correct

In C you should not test for overflow after the fact, because signed overflow is undefined behaviour and the compiler may delete your check. Use the checked builtins instead: __builtin_add_overflow in GCC and Clang, or C23's ckd_add from <stdckdint.h>. When you need a portable bit trick on unsigned values, the signed-overflow test is ((a ^ r) & (b ^ r)) with the top bit set. Subtraction is addition of the negation, with the usual INT_MIN exception: a - INT_MIN overflows for every non-negative a.

Sign extension, shifts and comparisons

Widening a signed value copies the top bit into every new bit. That is sign extension, and it keeps the value unchanged: 8-bit 11111011 (-5) becomes 32-bit 0xFFFFFFFB, still -5. Widening an unsigned value fills with zeros. Narrowing simply drops high bits, which is reduction modulo 2^n. It preserves the value only when the value fits.

Right shifts come in the same two flavours. An arithmetic shift copies the sign bit in and computes floor(x / 2^k). A logical shift brings zeros in. Note the rounding: -7 shifted right by one arithmetically is -4, while C, Java and Rust integer division gives -7 / 2 = -3, because division truncates toward zero. Python's // floors and matches the shift, so -7 // 2 is -4. Compilers that turn division by a power of two into a shift add a correction for negative inputs. When you do the strength reduction by hand, either the inputs are non-negative or you add the same correction yourself.

Comparisons are where the two readings visibly diverge. 0xFFFFFFFF is the biggest unsigned 32-bit value and the signed value -1. Flipping the top bit maps one order onto the other, which is how Java's Integer.compareUnsigned works: it compares a + MIN_VALUE with b + MIN_VALUE as signed values.

How languages expose it

The bits are the same everywhere. What differs between languages is what happens when a result does not fit:

A practical consequence: code ported from Java to C can go from "wraps" to "undefined" without a single character changing. Code ported from C to Python stops overflowing at all, so checksum and hash routines silently produce different values unless you mask after every operation.

Worked example: decoding a sensor field, and zigzag

A temperature sensor returns a 12-bit two's complement reading in the low bits of a 16-bit register, with 0.0625 degrees Celsius per least significant bit. The register reads 0x0F38. Read as unsigned, that is 3,896 × 0.0625 = 243.5 °C. That is wrong, and it is the classic bug. The top bit of the 12-bit field (bit 11) is set, so the true value is 3,896 - 4,096 = -200, which is -12.5 °C.

There are three idioms for sign-extending an n-bit field. All of them are worth knowing and testing exhaustively:

def sext_sub(x, n):                 # subtract 2^n when the sign bit is set
    x &= (1 << n) - 1
    return x - (1 << n) if x & (1 << (n - 1)) else x

def sext_xor(x, n):                 # branch-free: flip the sign bit, then subtract its weight
    m = 1 << (n - 1)
    return ((x & ((1 << n) - 1)) ^ m) - m

# In C, on a 32-bit int: shift the field to the top, then shift back arithmetically.
#   int32_t v = (int32_t)((uint32_t)raw << 20) >> 20;   // n = 12; relies on arithmetic >>

assert all(sext_sub(x, 12) == sext_xor(x, 12) for x in range(1 << 12))
print(sext_xor(0x0F38, 12) * 0.0625)    # -12.5

A related encoding shows why two's complement is a bad wire format for small negative numbers. As a varint, -1 is all ones and takes the maximum number of bytes. Protocol Buffers' sint32 and sint64 types therefore use zigzag encoding, which interleaves signs so that small magnitudes get small codes: 0, -1, 1, -2, 2 map to 0, 1, 2, 3, 4.

def zigzag32(n):   return ((n << 1) ^ (n >> 31)) & 0xFFFFFFFF    # n >> 31 is 0 or -1
def unzigzag32(z): return (z >> 1) ^ -(z & 1)

assert [zigzag32(v) for v in (0, -1, 1, -2, 2)] == [0, 1, 2, 3, 4]
assert all(unzigzag32(zigzag32(v)) == v for v in range(-70000, 70000))

The same representation drives integer quantization of neural networks. An int8 tensor holds -128 to 127, and many symmetric schemes use only -127 to 127 so the range is closed under negation and the scale is max|x| / 127. A signed int4 holds -8 to 7. Products of two int8 values fit easily in 16 bits, but dot products sum thousands of them, so kernels accumulate in int32. See INT8 quantization and INT4 quantization for the full schemes.

Failure modes

• abs(INT_MIN). The result is INT_MIN, still negative. Java's Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE, and in C it is undefined behaviour. Use Math.absExact, or widen before taking the absolute value.
• INT_MIN / -1. The true result does not fit. In C it is undefined behaviour, and on x86 the idiv instruction faults, which Linux delivers as SIGFPE. Java defines the result as INT_MIN. Rust panics.
• Midpoint overflow. (lo + hi) / 2 overflows once the indices pass 2^30. That bug sat for years in widely used binary search implementations. Use lo + (hi - lo) / 2, or (lo + hi) >>> 1 in Java.
• Negative hash index. h % n is negative for negative h in C and Java, and Math.abs(h) % n fails again when h is INT_MIN. Use Math.floorMod or mask with an unsigned type.
• Signed bytes. A byte 0xE9 read through a signed char or a Java byte sign-extends to -23 and indexes a table out of bounds. Mask with & 0xFF.
• Mixed comparisons. In C, -1 < 0u is false, because -1 converts to UINT_MAX. Enable -Wsign-compare.
• Post-hoc overflow checks. if (a + b < a) on signed ints can be optimised away. Use checked builtins.

Trade-offs

What to do next

1. Work the 4-bit wheel by hand: negate 3, add 7 + 1, subtract -8 - 1, and say which flag fires each time.
2. Write the add_n oracle above and use it to test any bit-level arithmetic you ship, exhaustively at 8 or 16 bits.
3. Turn on -Wsign-compare, plus -fsanitize=undefined in test builds of C and C++ code, and replace hand-rolled overflow checks with checked builtins.
4. Grep for abs(, % n on hashes, and (lo + hi) midpoints, and fix the INT_MIN and overflow cases.
5. Audit every place that decodes a packed field from hardware or a binary protocol for missing sign extension.
6. Continue with bit manipulation fundamentals and the bit hacks catalog, which lean on these identities throughout.