Coding Prep
Bit Manipulation
Operating directly on binary representations - XOR for cancellation, AND for masking, and the handful of tricks (power-of-2 check, lowest set bit, popcount) that cover most bit manipulation interview problems.
What is bit manipulation?
Every integer is stored in binary - a sequence of 0s and 1s. Bit manipulation operates on those individual bits using hardware-level operators (AND, OR, XOR, shift) instead of arithmetic. These operations are O(1) per call and often collapse problems that look O(n) into a single pass with O(1) extra space.
Python integers are arbitrary precision, so there is no 32-bit overflow to worry about. The main quirk is ~n = -(n+1) rather than a simple bit flip, because Python extends the sign bit infinitely. In Java and C++ interviews you must account for 32-bit sign bits and integer overflow, so it is worth noting the difference when asked in a cross-language context.
Bit manipulation is not a general-purpose technique. It appears in a specific cluster of problems: finding the unique element among duplicates (XOR cancellation), checking or setting flags (AND/OR with masks), counting set bits (popcount), and generating all subsets via bitmask enumeration.
The most important operator to internalize is XOR (^): a ^ a = 0 (self-inverse - any number cancels itself), a ^ 0 = a (identity - zero changes nothing), and XOR is commutative and associative (order never matters). These three properties together mean XORing a list of numbers cancels every even-count duplicate and leaves only the unique element.
Core operations
| Operation | Symbol | Example | Notes |
|---|---|---|---|
| AND | & | 5 & 3 = 1 (101 & 011 = 001) | Both bits must be 1; used for masking |
| OR | | | 5 | 3 = 7 (101 | 011 = 111) | Either bit is 1; used for setting bits |
| XOR | ^ | 5 ^ 3 = 6 (101 ^ 011 = 110) | Bits differ; used for toggling and cancellation |
| NOT | ~ | ~5 = -6 | Flips all bits; in Python ~n = -(n+1) |
| Left shift | << | 1 << 3 = 8 | Multiply by 2^k |
| Right shift | >> | 16 >> 2 = 4 | Divide by 2^k (floor) |
Key patterns
XOR cancellation
XOR every element together. Duplicate pairs cancel to 0; the single unique element remains. This works because XOR is commutative, associative, self-inverse (n ^ n = 0), and has 0 as its identity (n ^ 0 = n), so order of XOR never matters.
n ^ n ^ n = n, not 0. Confirm the problem guarantees even-count duplicates before applying this trick.Power-of-two check
A power of two has exactly one bit set: 1, 10, 100, 1000. Subtracting 1 flips that bit and sets all lower bits: 8 - 1 = 7 means 1000 - 1 = 0111. ANDing n & (n-1) clears the lowest set bit; if the result is 0, exactly one bit was set.
n > 0 - 0 & (0 - 1) evaluates to 0 in Python due to arbitrary-precision arithmetic, which would incorrectly classify 0 as a power of two without the guard.Bit masking
Use a mask 1 << k to target bit position k (0-indexed from the right). Four independent operations - get, set, clear, toggle - each takes one line and one mask.
n & (n-1) clears the lowest set bit; n & (-n) isolates it - these two companion tricks appear constantly. n & (n-1) removes the lowest 1-bit (used in popcount loops). n & (-n) returns a number with only the lowest 1-bit of n set (used in Fenwick trees and to iterate over set bits one by one).Bitmask enumeration
For a set of n elements, every subset corresponds to an n-bit integer from 0 to 2^n - 1. Bit k is set if and only if element k is in the subset. Iterate all 2^n subsets by looping masks from 0 to (1 << n) - 1.
Canonical examples
Power of two
Is n an exact power of two? A power of two has exactly one bit set: 1, 10, 100, 1000. Subtracting 1 flips that bit and sets all lower bits (8 - 1 = 7 means 1000 → 0111). ANDing n & (n - 1) clears the lowest set bit; if the result is 0, exactly one bit was set.
Count set bits (Hamming weight)
Count the number of 1-bits in an integer. The naive approach shifts through every bit position one at a time. The Brian Kernighan trick uses n &= n - 1 to clear the lowest set bit each iteration - the loop runs exactly popcount(n) times rather than 32 times, doing less work on sparse integers.
bin(n).count('1') is correct but explains nothing - in an interview, use the Kernighan loop to show you understand the bit structure. The string conversion approach is O(log n) string allocation and misses the point of the problem entirely.When to reach for bit manipulation
- The problem says "all elements appear twice except one" or "find the element that appears once" - XOR cancellation.
- You need to check if a number is a power of two or count how many times a number is divisible by 2.
- The problem involves subset enumeration where n is small (
n <= 20) - iterate bitmasks from 0 to 2^n - 1. - You need to pack multiple boolean flags into a single integer - permissions, visited states in bitmask DP.
- The problem involves swapping two values without a temp variable -
a ^= b; b ^= a; a ^= b. - The problem mentions XOR explicitly in the statement, or asks about Hamming distance between two numbers.
- A DP state tracks which elements have been visited and n is small - encode the state as a bitmask integer.
Practice problems
- Single Number - XOR cancellation of pairs; O(1) space.
- Number of 1 Bits - Kernighan loop;
n & (n-1)trick. - Power of Two -
n & (n-1) == 0check with the zero guard. - Counting Bits - DP using
popcount(n) = popcount(n >> 1) + (n & 1). - Single Number II - Every element appears 3 times except one; requires bit counting modulo 3.
- Reverse Bits - Shift and mask to reverse a 32-bit integer bit by bit.
Challenges that exercise this
Practical multi-level challenges that put this primer to work.
Done reading? Mark it so it sticks in your dashboard.