Bit Manipulation
Think of a row of light switches, each either on or off. A lot of clever tricks in computing come from realizing you can flip, check, or compare those switches directly instead of doing math on the number they represent. That's bit manipulation: working with the actual 1s and 0s under a number, rather than the number as a whole. Bit manipulation problems test whether you understand what's really happening under a language's integer abstraction. They come up because a handful of XOR/AND/OR tricks turn O(n) extra-space problems into O(1) space ones, and interviewers use them as a quick signal for how deep your computer science fundamentals go.
Bitwise operations
The core operators, and what they mean bit by bit:
a & b # AND: 1 only where both bits are 1 — used for masking / checking a bit
a | b # OR: 1 where either bit is 1 — used for setting a bit
a ^ b # XOR: 1 where bits differ — used for toggling / finding differences
~a # NOT: flips every bit — in Python, ~a == -a - 1 (two's complement)
a << k # left shift: multiply by 2^k
a >> k # right shift: divide by 2^k (floor, arithmetic shift for negative ints in Python)Useful bit-twiddling idioms worth having memorized:
n & (n - 1) # clears the lowest set bit — used to count set bits, check power of 2
n & (-n) # isolates the lowest set bit
n | (1 << k) # sets bit k
n & ~(1 << k) # clears bit k
n ^ (1 << k) # toggles bit k
(n >> k) & 1 # reads bit kn & (n - 1) == 0 (for n > 0) is the fastest power-of-2 check: a power of 2 has exactly one set bit, and subtracting 1 flips every bit below it, so ANDing the two together always gives zero.
Remember: AND masks, OR sets, XOR toggles, and
n & (n-1)clears the lowest set bit. These six lines cover most bit-manipulation interview questions.
Two's complement
Negative integers are represented as two's complement in essentially every language with fixed-width integers: to negate n, flip every bit and add 1 (~n + 1 == -n). That's why ~a == -a - 1 in Python even though Python integers are conceptually unbounded; Python still models bitwise NOT as if it were operating on an infinite two's-complement representation.
Python has a quirk worth knowing for interviews: unlike Java or C++, Python integers have no fixed bit width, so operations like n >> 1 on a negative number keep sign-extending forever, and there's no native 32-bit overflow wraparound. Problems like Reverse Bits and Sum of Two Integers explicitly need you to simulate fixed-width behavior with masking:
MASK32 = 0xFFFFFFFF # mask to simulate a 32-bit unsigned register
def to_signed_32(n: int) -> int:
n &= MASK32
# if the sign bit (bit 31) is set, interpret as negative
return n if n < 0x80000000 else n - 0x100000000Remember: Python integers never overflow on their own. If a problem needs 32-bit behavior, you have to fake it yourself with a mask.
Common patterns
XOR self-cancellation (a ^ a == 0, a ^ 0 == a, and XOR is commutative and associative): XOR-ing an array where every element appears twice except one leaves only the unpaired element, because every pair cancels to 0. That's the entire trick behind Single Number.
Counting set bits: n & (n - 1) repeatedly clears the lowest set bit. Loop until n == 0, counting iterations. This runs in O(popcount) time rather than O(32) for checking every bit position, which matters when n is sparse.
Missing number via XOR: XOR-ing 0..n together with every element of an n-length array (which is missing exactly one value from 0..n) cancels every present value, leaving the missing one behind. This avoids the overflow risk of a sum-based approach (n*(n+1)/2 - sum(nums)), which matters in fixed-width-integer languages even though it's a non-issue in Python.
Remember: XOR cancels pairs to zero and leaves singles untouched. That one fact solves Single Number and Missing Number both.
Number of 1 Bits
LeetCode 191 · Number of 1 Bits · Bit · Hamming weight
Intuition: Count set bits by repeatedly clearing the lowest one with n & (n - 1) until n becomes 0. The number of clears equals the number of set bits.
Approach: Loop while n != 0; each iteration does n &= n - 1 and increments a counter.
def hamming_weight(n: int) -> int:
count = 0
while n:
n &= n - 1 # clears the lowest set bit
count += 1
return countComplexity: O(k) time where k is the number of set bits, not 32, better than a naive O(32) bit-by-bit scan on sparse inputs. O(1) space.
Common mistakes: using n >>= 1 combined with n & 1 in a fixed 32-iteration loop. That's correct but strictly worse than the n & (n-1) trick when bits are sparse. Also, forgetting Python has no fixed width, so a naive right-shift loop on a value treated as "signed 32-bit" needs masking to behave correctly.
Remember: each
n & (n-1)removes exactly one set bit. Count the removals, not the bit positions.
Reverse Bits
LeetCode 190 · Reverse Bits · Bit · Bit swapping
Intuition: Build the result bit by bit: take the lowest bit of the input, place it as the highest bit of the output (shifted into position), then shift the input right and repeat for all 32 positions.
Approach: Loop 32 times; each iteration extracts n's lowest bit, shifts it into the correct position of result, then shifts n right by one.
def reverse_bits(n: int) -> int:
result = 0
for i in range(32):
bit = (n >> i) & 1
result |= bit << (31 - i)
return resultComplexity: O(32) = O(1) time (fixed width), O(1) space.
Common mistakes: forgetting the loop must run exactly 32 times regardless of how many leading zero bits n has, since this is a fixed-width problem, not a variable-length one. Also, an off-by-one in the shift amount: it's 31 - i, not 32 - i.
Remember: the loop always runs exactly 32 times. Leading zeros in the input don't shorten it.
Single Number
LeetCode 136 · Single Number · Bit · XOR trick
Intuition: Every element except one appears exactly twice. XOR-ing the whole array cancels every paired element to 0, leaving only the unpaired one, since XOR is commutative and associative, so the order pairs cancel in doesn't matter.
Approach: Single pass, XOR-accumulate into a running result.
def single_number(nums: list[int]) -> int:
result = 0
for num in nums:
result ^= num
return resultComplexity: O(n) time, O(1) space. Strictly better than a hash-set approach (O(n) space), which is the "obvious" first instinct.
Common mistakes: reaching for a Counter/hash-set solution first without noticing the O(1)-space XOR trick applies whenever "every element appears twice except one" is the setup. Also, trying to force the XOR trick onto a variant where elements appear three times except one (LeetCode 137), which needs a different bit-counting technique since XOR alone doesn't work there.
Remember: "everything appears twice except one" is the exact trigger phrase for the XOR trick. Don't reach for a hash set first.
Missing Number
LeetCode 268 · Missing Number · Bit · XOR
Intuition: An array of length n contains distinct values from 0 to n, missing exactly one. XOR every array value together with every value from 0 to n inclusive: every present number cancels with its own index/value pairing, leaving only the missing number.
Approach: Initialize result = n (accounts for the index-n term that has no matching array index), then XOR in i ^ nums[i] for each index.
def missing_number(nums: list[int]) -> int:
result = len(nums) # pre-seed with n, since indices only go 0..n-1
for i, num in enumerate(nums):
result ^= i ^ num
return resultComplexity: O(n) time, O(1) space.
Common mistakes: using the arithmetic sum formula (n*(n+1)//2 - sum(nums)), which is fine in Python but worth contrasting with XOR: in fixed-width-integer languages, the sum formula risks overflow for large n, while XOR never does, which is why XOR is the "safer general" answer even though both are O(n)/O(1) in Python. Also, miscounting the range: you must XOR indices 0..n-1 plus values, seeded with n, not 0..n.
Remember: seed the running XOR with
nbefore the loop, since indexnitself never appears as an array position.