Think of a number as a row of switches
Every integer is stored as a fixed row of bits, each either 1 (on) or 0 (off). Bit manipulation treats that row as data you can inspect and edit position by position, rather than as a single arithmetic value. Because a CPU runs each of these operations as one hardware instruction, they are about as cheap as computation gets.
The mental model that makes everything else click: a 32-bit integer is 32 tiny switches. Most bit tricks are just clever ways to ask 'which switches are on?' or to flip a chosen switch without touching the others. Watching those switches change one step at a time is far more intuitive than memorizing the identities cold.
The five operators and the idea of a mask
There are only five tools. AND (&) keeps a bit only where both inputs are 1, so it tests or clears bits. OR (|) sets a bit where either input is 1, so it turns bits on. XOR (^) sets a bit where the two differ, so it toggles — and it is self-inverse, meaning a ^ a = 0 and a ^ 0 = a. NOT (~) flips every bit. Shifts (<< and >>) slide bits left or right, which multiplies or divides by powers of two.
A mask is just a purpose-built integer that isolates the bits you care about. The workhorse is 1 << k, a single 1 at position k. With it you can test a bit (x & (1 << k)), set it (x | (1 << k)), clear it (x & ~(1 << k)), or toggle it (x ^ (1 << k)). Almost every bit problem reduces to building the right mask and applying one of these four moves.
The classic patterns interviewers love
Single number: XOR every element of an array together. Equal pairs cancel to 0 and the lone unmatched value survives — one pass, no extra memory. Counting set bits (popcount): Brian Kernighan's trick n &= n - 1 clears the lowest set bit each iteration, so the loop runs exactly once per 1-bit. Power of two: a power of two has exactly one set bit, so n > 0 and (n & (n - 1)) == 0 answers it in one line.
Two more worth knowing: n & -n isolates the lowest set bit, and a bitmask can stand in for a small set of items so you can iterate over all subsets. These few identities cover the large majority of bit-manipulation questions you will actually meet.
def single_number(nums):
# XOR cancels equal pairs; the unique value survives
result = 0
for n in nums:
result ^= n
return result
def count_set_bits(n):
# Brian Kernighan: n & (n - 1) clears the lowest set bit
count = 0
while n:
n &= n - 1
count += 1
return count
def is_power_of_two(n):
# A power of two has exactly one set bit
return n > 0 and (n & (n - 1)) == 0Kernighan's loop is fastest when few bits are set (best case a couple of iterations) and worst case runs once per bit, up to the word width of 32 or 64. A plain bit-by-bit scan is always O(word size) regardless of input.
When to use it
- Tracking a small set of on/off flags compactly — a bitmask instead of a boolean array or hash set, including bitmask DP over subsets.
- A problem hinges on pairing, cancellation, or parity — XOR to find the unique number, spot a missing or duplicated value, or swap two variables without a temp.
- You need fast checks tied to powers of two — testing, setting, or clearing a specific bit, checking if a number is a power of two, or aligning to a boundary.
- Tight memory or performance constraints where replacing arithmetic with shifts and masks genuinely matters (embedded, hashing, low-level systems).
Watch out for
- Operator precedence bites: &, |, and ^ bind looser than == and + in C, Java, JavaScript, and Python, so x & 1 == 0 parses as x & (1 == 0). Always parenthesize the comparison.
- Signed shifts and width surprises: right-shifting negatives, or shifting by more than the type's width, is language-dependent (Java's >> vs >>>, JavaScript coercing to 32 bits, undefined behavior in C). Python ints are arbitrary precision, so ~ and shifts behave differently than fixed-width languages.
- Reaching for bit tricks when they don't help — cleverness that hurts readability without improving complexity. Use them where they truly simplify or are required, not to show off.
Bit manipulation is the classic "clever trick" round — problems that look hard until you spot the one-line bitwise insight: single number, counting set bits, power of two, subset enumeration via bitmask, XOR swaps. Interviewers rarely want obscure hacks; they want proof that you understand what AND, OR, XOR, and shifts actually do, that you can build and apply a mask, and that you reason about edge cases like zero, negatives, and overflow. Being able to explain why n & (n - 1) clears the lowest set bit, rather than just reciting it, is what separates memorization from real understanding. It also shows up as a component inside larger problems — bitmask dynamic programming over subsets, hashing, and deduplication.