Two's Complement

Why negative numbers need a trick

A register is just a row of bits. To store −5 we have to agree on which bit pattern means −5. The method that won is two’s complement, because it lets the CPU use one adder for positive and negative numbers alike.

The weights idea

In an 8-bit unsigned number the bit weights are 128, 64, 32, 16, 8, 4, 2, 1. In two’s complement the leftmost weight becomes negative: −128, 64, 32, 16, 8, 4, 2, 1.

So 11111011 = −128 + 64 + 32 + 16 + 8 + 2 + 1 = −5.

Negating a number

to get −x:
    1. write x in binary (n bits)
    2. invert every bit        (one's complement)
    3. add 1

Example: −37 in 8 bits

Check: −128 + 64 + 16 + 8 + 2 + 1 = −37.

Range

With n bits you can store −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. For 8 bits that is −128 to 127, and for 4 bits −8 to 7. There is only one zero (0000), which is why the range is not symmetric.

Subtraction for free

To compute a − b the CPU adds a to the two’s complement of b. No separate subtractor is needed, only the adder shown in the ripple-carry adder lesson.

Code

def twos_complement(x, bits=8):
    return format(x & ((1 << bits) - 1), f'0{bits}b')

def from_twos_complement(s):
    n = len(s)
    value = int(s, 2)
    return value - (1 << n) if s[0] == '1' else value

print(twos_complement(-37))              # 11011011
print(from_twos_complement('11111011'))  # -5

Common mistakes

• Forgetting to add 1 after inverting. Inverting alone gives the one’s complement, which is off by one.
• Using too few bits. −37 does not fit in 6 bits (range −32 to 31).
• Treating the sign bit as “just a minus sign”. It is a bit with weight −2ⁿ⁻¹, and the other bits change meaning too.
• Mixing up the range: −128 exists in 8 bits, but +128 does not.