Bit manipulation is a small toolkit that turns certain problems from clever into trivial. The operators are simple, but a handful of idioms — XOR to cancel pairs, masks to isolate a bit, shifts to build powers of two — show up so often that knowing them cold is worth the twenty minutes it takes to memorize them. It is also the one topic where candidates freeze not because the problem is hard, but because they cannot recall the exact mask, so the payoff for a little rote practice is unusually high.
The good news is that the surface area is tiny. There are five operators, roughly six idioms, and a short list of problems that recombine them. This guide covers all three so that when a bitwise question appears — often disguised as an array or math problem — you recognize the shape and reach for the right one-liner instead of reinventing it under pressure.
The bitwise operators
Everything is built from five operators. Think of an integer as a row of bits and each operator as acting column by column.
| Operator | Symbol | Result bit is 1 when... |
|---|---|---|
| AND | & | both input bits are 1 — used to mask and test bits |
| OR | | | either input bit is 1 — used to set bits |
| XOR | ^ | the bits differ — used to toggle and cancel |
| NOT | ~ | flips every bit (~x == -x - 1 in two's complement) |
| Shift | << >> | move bits left/right; 1 << i builds a single-bit mask |
A left shift by i multiplies by 2i; a right shift divides by 2i (floor, for non-negative values). Python integers are arbitrary precision, so there is no fixed 32-bit overflow — something to keep in mind on problems that assume fixed-width words.
The tricks worth memorizing
Almost every bit problem reduces to one of these idioms. The mask 1 << i isolates a single position; combine it with an operator to test or change that bit.
# check bit i -> 1 if set, else 0
bit = (x >> i) & 1
x = x | (1 << i) # set bit i to 1
x = x & ~(1 << i) # clear bit i to 0
x = x ^ (1 << i) # toggle bit i
lowest = x & -x # isolate the lowest set bit
x = x & (x - 1) # clear the lowest set bita ^ a == 0 (a value cancels itself), a ^ 0 == a (XOR with zero is identity), and XOR is commutative and associative (order does not matter). Together they mean XOR-ing a whole array makes every duplicated value vanish.
Worked examples
Single Number
Problem: Every element in an array appears twice except one. Find that one.
XOR everything together. The pairs cancel to 0 and the lone value survives — no hash set, no extra memory.
def singleNumber(nums):
result = 0
for n in nums:
result ^= n
return resultO(n) time, O(1) space. This is the canonical demonstration of the XOR cancellation identity.
Number of 1 Bits
Problem: Count the set bits (the Hamming weight) of an integer.
Brian Kernighan's trick: x & (x - 1) clears the lowest set bit, so the loop runs once per set bit instead of once per total bit.
def hammingWeight(x):
count = 0
while x:
x &= x - 1 # drop the lowest set bit
count += 1
return countO(k) time where k is the number of set bits, O(1) space. In Python you could also write bin(x).count("1"), but the loop shows you understand the mechanism.
Power of Two
Problem: Return whether a positive integer is a power of two.
A power of two has exactly one set bit, so x & (x - 1) clears that bit and yields 0. Guard against non-positive inputs first.
def isPowerOfTwo(x):
return x > 0 and (x & (x - 1)) == 0O(1) time and space. The same x & (x - 1) idiom that counts bits also tests for a single bit.
Subsets via Bitmask
Problem: Generate all subsets (the power set) of a list of n elements.
Each integer from 0 to 2**n - 1 encodes a subset: bit i set means element i is included. Loop over all masks and read their bits.
def subsets(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 .. 2^n - 1
subset = [nums[i] for i in range(n) if (mask >> i) & 1]
result.append(subset)
return resultO(2n · n) time and space — unavoidable, since there are 2n subsets. Bitmasks give a clean, iterative alternative to recursion and are the foundation of bitmask dynamic programming.
Complexity at a glance
Bit tricks are usually about constant-factor elegance rather than changing the asymptotic class, but several genuinely improve the complexity over a naive approach. Single Number replaces an O(n) hash set with O(1) space; Number of 1 Bits drops from scanning all bits to scanning only the set ones. The subset generator is exponential by necessity, since the output itself is exponential.
| Problem | Time | Space | Key idea |
|---|---|---|---|
| Single Number | O(n) | O(1) | XOR cancels pairs |
| Number of 1 Bits | O(k set bits) | O(1) | x & (x - 1) |
| Power of Two | O(1) | O(1) | single set bit |
| Subsets (bitmask) | O(2ⁿ · n) | O(2ⁿ · n) | integer as subset |
When you present a bit-based solution, call out explicitly what it buys you — "constant space instead of a hash set" or "we only touch set bits" — because the whole reason to reach for bit manipulation is the resource win, and interviewers want to hear that you know it.
Variations & pitfalls
- Operator precedence. Bitwise operators bind looser than comparisons in Python, so parenthesize: write
(x >> i) & 1, notx >> i & 1. - Signed vs fixed-width. Python ints are unbounded; if a problem assumes 32-bit wraparound, mask with
& 0xFFFFFFFFand handle the sign explicitly. - XOR needs the exact frequency structure. The single-number trick assumes every other element appears exactly twice. Numbers appearing three times need a different (bit-counting) approach.
- Off-by-one on shifts. Bit positions are zero-indexed, so the range of masks for n bits is
0to(1 << n) - 1.
Spot the bit trick with live AI support
CoPilot Interview surfaces the optimal pattern and a working solution with Big-O in about 4 seconds during real Zoom and Teams calls. Free for Windows and macOS, invisible on screen-share.
Download freeFAQ
What bitwise operations do I need for interviews?
AND (&), OR (|), XOR (^), NOT (~), and the left/right shifts (<<, >>). Most interview tricks are built from these: masks with AND and OR, toggling and cancellation with XOR, and building powers of two with shifts.
How do I check, set, or clear a single bit?
To check bit i, test (x >> i) & 1. To set it, x | (1 << i). To clear it, x & ~(1 << i). To toggle it, x ^ (1 << i). The mask 1 << i isolates the position you care about.
Why does XOR solve the single number problem?
XOR of a value with itself is 0, and XOR with 0 leaves a value unchanged. So XOR-ing every element in an array where each number appears twice except one cancels the pairs and leaves the unique value, in O(n) time and O(1) space.
How do I count the set bits in a number?
Use Brian Kernighan's trick: repeatedly apply x &= x - 1, which clears the lowest set bit each time, counting one iteration per set bit. It runs in O(number of set bits) rather than O(total bits).
How do bitmasks represent subsets?
For a set of n elements, an integer from 0 to 2^n - 1 encodes a subset: bit i being 1 means element i is included. Looping over all such integers and reading their bits enumerates every subset in O(2^n * n) time.