Binary & Two's Complement

Binary & two's complement

The mental model behind every bitwise problem. Read once, then the idioms in cheatsheet.md make sense.

Reading binary (unsigned)

Binary is base-2 positional notation. Each bit is a power of 2, counting right to left from 2^0:

0b1011  =  1·2³ + 0·2² + 1·2¹ + 1·2⁰  =  8 + 0 + 2 + 1  =  11
           bit3   bit2   bit1   bit0

Bit 0 (rightmost) = least significant bit (LSB), worth 1 — decides odd/even.
Leftmost = most significant bit (MSB), worth the most.
0b is Python's binary literal prefix: 0b1011 == 11.
n bits cover the range 0 .. 2^n - 1. One byte (8 bits) → 0..255.

bin(11)            # '0b1011'   (string, with prefix)
int('1011', 2)     # 11         (parse base-2 string)
format(11, 'b')    # '1011'     (no prefix)
format(11, '08b')  # '00001011' (zero-padded to 8 wide)

x << 1   # append a 0 bit  → ×2       0b1011 (11) → 0b10110 (22)
x >> 1   # drop last bit   → //2      0b1011 (11) → 0b101   (5, floor)
x << k   # ×2^k
x >> k   # //2^k  (floor division)

Two's complement (signed, fixed width)

To store negatives in a fixed number of bits, hardware uses two's complement. In an n-bit system the top bit carries the sign (0 = non-negative, 1 = negative), and to negate a value you flip all bits, then add 1.

8-bit, building -5:

 5 = 00000101
flip 11111010
 +1  11111011   = -5

Why flip-and-add-1: it makes ordinary binary addition produce the right answer. 5 + (-5) should be 0:

  00000101   (5)
+ 11111011   (-5)
= 100000000  → the 9th bit overflows out of 8 bits → 00000000 = 0  ✓

Reading a negative value back: the MSB has a negative weight, the rest stay positive.

11111011 = -2⁷ + 2⁶ + 2⁵ + 2⁴ + 2³ + 2¹ + 2⁰
         = -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5

Range of n-bit two's complement is -2^(n-1) .. 2^(n-1) - 1 — asymmetric (one extra negative). 8 bits → -128..127; 32 bits → -2147483648 .. 2147483647.

Python's twist: infinite-width two's complement

Python ints are arbitrary precision, so there's no fixed width to flip within. The model is infinite two's complement:

non-negative → infinitely many leading 0s: 5 = ...00000101
negative → infinitely many leading 1s: -5 = ...11111011

Bitwise ops behave as if the sign bit extends forever:

-1          # ...11111111   (all ones)
-1 & 0xFF   # 255   — mask 8 bits out of the infinite ones
-1 >> 1     # -1    — arithmetic shift; sign extends, stays all ones
~5          # -6    — flip every bit
~0          # -1

The identity worth memorizing: ~n == -n - 1.

`bin()` of a negative lies to you

bin() does NOT print two's complement — it prints sign-magnitude, a minus sign glued to the magnitude's bits:

bin(5)    # '0b101'
bin(-5)   # '-0b101'   ← NOT the ...11111011 pattern that & | ^ actually operate on

So a negative's display and its bitwise behavior disagree — the classic trap. To see the true fixed-width pattern, mask first:

bin(-5 & 0xFF)   # '0b11111011'  — the real 8-bit two's complement

Masking to fixed width — when LC forces it

Problems that say "32-bit signed integer" can break a naive bit loop, because on a negative the leading 1s never run out:

while n:            # n = -1 → -1 >> 1 is still -1 → INFINITE LOOP
    count += n & 1
    n >>= 1

Mask into 32 bits first — now it's finite, non-negative, and you're treating the bits as the unsigned representation:

n &= 0xFFFFFFFF     # 32 one-bits; loop now terminates after ≤32 iterations

To re-interpret a 32-bit result as signed afterward: if bit 31 is set, subtract 2**32.

Binary & Two's Complement