Binary, operators & bit tricks

How integers are stored, the six bit operators, and the tricks that show up everywhere. · 12 min read

Concept

A fixed-width integer is just a row of bits with place values …, 8, 4, 2, 1. Bit manipulation works on those bits directly — it's fast (single CPU instructions), compact, and the natural language for sets, flags, and parity.

Two's complement

Signed integers use two's complement: the top bit is the sign, and negating a number is "invert all bits, then add 1". This is why -x == ~x + 1, why x & -x isolates the lowest set bit, and why signed overflow wraps around. In an n-bit type the range is -2ⁿ⁻¹ … 2ⁿ⁻¹ - 1.

The six operators

• a & b — AND: 1 where both are 1 (mask/keep bits).
• a | b — OR: 1 where either is 1 (set bits).
• a ^ b — XOR: 1 where they differ (toggle/cancel).
• ~a — NOT: flip every bit.
• a << k — left shift: multiply by 2ᵏ.
• a >> k — right shift: divide by 2ᵏ (floor for non-negatives).

Interactive visualization: Apply a bit operation column by column — step through it frame by frame on this page.

Standard bit tricks

x & (1 << i)        // test bit i (non-zero if set)
x | (1 << i)        // set bit i
x & ~(1 << i)       // clear bit i
x ^ (1 << i)        // toggle bit i
x & -x              // lowest set bit (as a value)
x & (x - 1)         // clear the lowest set bit
x && !(x & (x - 1)) // is x a power of two?
__builtin_popcount(x) // number of set bits (GCC)

Interactive visualization: x & -x isolates the lowest set bit — step through it frame by frame on this page.

XOR superpowers

XOR is its own inverse (a ^ a = 0, a ^ 0 = a), so it cancels pairs. That solves "find the element that appears once", swapping without a temp, and parity/prefix-XOR problems. Counting set bits with the i >> 1 recurrence is a tiny DP (see the problems).

Practice: Single Number (Easy) — Every value appears twice except one — find it with XOR.

Practice: Counting Bits (Medium) — Popcount for every number 0..n in O(n) using a bit DP.