💕 Two's Complement

Computers represent integers in binary with a finite width of . If we’re simply representing unsigned integers, the least significant bit (LSB) is , and the most significant bit (MSB) is .

However, with signed integers, we need some way to indicate if the value is negative. Two’s complement is a trick that makes certain arithmetic operations valid for both unsigned and signed binary: all bits are as normal, except the MSB is .

Intuitively, this representation comes from the insight that due to the finite width , we can imagine that overflow or underflow “cycles around.” Then, for example with , if we want to compute , we can imagine the as cycling around, . Using this, we have

To negate a number, we have a simple rule:

where is the flipped bits of . This arises from the equation above, since

and we notice that is the flipped bits .