Bitwise AND, OR, and XOR: What They Do and Why Interviews Test Them
- Bitwise AND (
&) keeps a bit only when both columns are 1;n & (n-1)strips the lowest set bit and is the basis for power-of-two checks and Hamming weight loops. - Bitwise OR (
|) sets a bit when either input is 1; it's the accumulator for building bitmask state in bitmask DP problems. - XOR (
^) outputs 1 when bits differ; its self-inverse property (n ^ n = 0) solves "single number" and "missing number" in O(n) time and O(1) space. - Shift operators (
1 << k) produce single-column masks, making targeted check, set, clear, and toggle operations precise and readable. - Six core idioms cover nearly every bit-manipulation interview problem: check, set, clear, toggle a bit, strip the lowest set bit (
n & (n-1)), and isolate the lowest set bit (n & -n). - Bitwise operations run in O(1); the complexity budget lives in the surrounding loop, not the operation itself.
- Three problem signals point to bit solutions: "find the unique element," "O(1) extra space" with integers in range, and "all subsets or combinations."
You have seen n & (n - 1) in someone's solution. You nodded. You moved on. You did not ask what it does because that would mean admitting you did not know, and you were not about to do that in a code review.
Then the interview came. The interviewer asked you to count set bits efficiently. You wrote the naive loop. They asked if there was a faster way. You said "maybe use a lookup table?" There was a pause. A very specific kind of pause.
Here is what n & (n - 1) actually does, plus the full foundation behind it.
Your CPU Thinks in Columns
Every integer in memory is a sequence of bits, each either 0 or 1. The number 13, in 4-bit binary, is 1101. The number 9 is 1001. When you do a bitwise operation, the CPU applies the rule independently to each column, left to right, all at once.
That "column by column" idea is everything. Once you internalize it, all three operators stop looking like magic and start looking obvious.
A quick reference:
| Decimal | Binary (8-bit) |
|---|---|
| 0 | 0000 0000 |
| 1 | 0000 0001 |
| 5 | 0000 0101 |
| 9 | 0000 1001 |
| 13 | 0000 1101 |
| 255 | 1111 1111 |
Here is what that looks like when all three operators work on the same two inputs at once:
AND: The Bouncer That Wants Both IDs
The & operator outputs a 1 in a column only when both inputs have a 1 there. One 0 anywhere and the whole column goes dark.
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
13 & 9:
1101 (13)
& 1001 ( 9)
------
1001 ( 9)
AND is a mask. You use it to check or clear specific bits.
n = 13 # 1101 if n & 4: # 4 = 0100, checks bit 2 print("bit 2 is set") # Strip the lowest set bit n = 12 # 1100 result = n & (n - 1) # 1100 & 1011 = 1000 = 8
Here is why n & (n - 1) works. Subtracting 1 from n flips the lowest set bit to 0 and turns everything below it to 1. AND-ing with the original n then zeroes out exactly that bit and leaves the rest untouched. Every call to n & (n - 1) strips one set bit. That is the whole trick.
n & (n - 1) strips the lowest set bit from n every time. That single operation solves Number of 1 Bits, Power of Two, and Counting Bits. If n & (n - 1) == 0, n is a power of two because powers of two have exactly one bit set, and stripping it leaves zero.
OR: Sets Bits and Minds Its Business
The | operator outputs a 1 when at least one input has a 1. It does not turn things off.
| A | B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
13 | 9:
1101 (13)
| 1001 ( 9)
------
1101 (13)
OR sets bits without touching the others. It is the complement of AND: AND reaches in to clear or check, OR reaches in to set.
n = 9 # 1001 result = n | 2 # 1001 | 0010 = 1011 = 11 (sets bit 1) # Build a bitmask for a subset mask = 0 mask |= (1 << 0) # set bit 0 -> 0001 mask |= (1 << 2) # set bit 2 -> 0101
OR is the workhorse in bitmask DP and anywhere you accumulate a set of flags into a single integer. If you have ever wondered how TSP solutions represent "which cities have been visited" without a boolean array, OR is how.
XOR: The One That Actually Blows Minds
XOR (exclusive OR, ^) outputs 1 when the inputs differ, 0 when they are the same. Two 0s: output 0. Two 1s: output 0. One of each: output 1.
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
13 ^ 9:
1101 (13)
^ 1001 ( 9)
------
0100 ( 4)
Three Properties That Power Interview Solutions
Self-inverse: n ^ n = 0. A number XORed with itself is always zero.
Identity: n ^ 0 = n. XORing with zero changes nothing.
Commutative and associative: order does not matter, so duplicates cancel anywhere in the sequence.
These three together are why XOR solves "find the single number" in O(n) time and O(1) space. You have a list where every number appears twice except one. XOR the whole thing. Every pair cancels itself out. What is left is the lone survivor.
nums = [2, 1, 4, 1, 2] result = 0 for n in nums: result ^= n print(result) # 4
No hash map. No sort. No extra space. No second pass. XOR is the reason that solution exists and the reason you look slightly unhinged when you explain it to someone who has not seen it before.
The same logic handles "find the missing number in [0, n]." XOR all indices from 0 to n, then XOR every value in the array. Everything that appears in both cancels, and the missing number is what remains.
def missing_number(nums: list[int]) -> int: result = len(nums) for i, n in enumerate(nums): result ^= i ^ n return result
For more patterns built on the self-inverse property, see XOR in Coding Interviews.
Bit Shifts: The Quiet Workhorse
The idioms table below uses 1 << k. Shifts need a sentence before they show up there.
<< moves bits left by k positions, padding the right with zeros. 1 << k produces a single 1 in column k and zeros everywhere else. That is exactly the mask you need to target one column with AND, OR, or XOR.
1 << 0 # 0000 0001 (targets bit 0) 1 << 2 # 0000 0100 (targets bit 2) 1 << 7 # 1000 0000 (targets bit 7)
>> shifts right: n >> k divides n by 2^k rounding down. Useful for pulling a specific bit to position 0 so you can inspect it directly.
The Six Idioms That Cover Most Problems
With AND, OR, XOR, and shifts in hand, these six patterns cover the overwhelming majority of bit manipulation interview problems:
| Goal | Operation | Example |
|---|---|---|
Check if bit k is set | n & (1 << k) | n & 4 checks bit 2 |
Set bit k | n | (1 << k) | n | 4 forces bit 2 to 1 |
Clear bit k | n & ~(1 << k) | n & ~4 forces bit 2 to 0 |
Toggle bit k | n ^ (1 << k) | n ^ 4 flips bit 2 |
| Strip lowest set bit | n & (n - 1) | Kernighan's bit count trick |
| Isolate lowest set bit | n & (-n) | Used in Fenwick trees |
These show up directly in bitmask problems. The ~ is bitwise NOT, which flips every bit and lets AND clear instead of set.
O(1) Time, But the Loop Is What Counts
Bitwise operations run in O(1). The CPU applies the column rules in parallel across all bits in a single clock cycle. Space is O(1) because you are operating on values in registers, not allocating anything.
The complexity comes from the loops around the operations, not the operations themselves. Counting set bits with n & (n - 1) in a loop runs in O(number of set bits), not O(bit width). For sparse integers, that is genuinely faster than checking every column.
def count_set_bits(n: int) -> int: count = 0 while n: n &= (n - 1) # strips one set bit per iteration count += 1 return count
An integer with three set bits exits the loop in three iterations, regardless of how many total bits the type has.
Why Interviews Test This
Bit operations signal machine-level understanding. Most engineers working in high-level languages never think below integers. Knowing that n & (n - 1) strips the lowest set bit, and being able to explain why, shows you understand how data actually sits in memory. That is rarer than it sounds.
They also produce provably optimal solutions. When a problem has an O(n) time, O(1) space answer via XOR, there is no room to improve. The interviewer already knows the clean answer exists. They are watching to see whether you find it or reach for a hash map and miss the insight.
At harder difficulty, bit operations are the building blocks for bitmask DP. You represent state as an integer, use OR to add elements to a set, and AND to check membership. You cannot do those problems without fluency in the basics. Trying to reason about TSP in an interview while also trying to remember what |= does is not a great position to be in.
The most commonly tested patterns, roughly in order of frequency:
- Single number (XOR self-inverse property)
- Missing number in a range (XOR over indices and values)
- Power of two check (
n & (n - 1) == 0) - Bit count loops (Kernighan's trick)
- Subset generation via bitmasks (OR to build, AND to query)
When to Reach for Bits
Three signals in the problem statement that should stop you before you open a defaultdict:
"Find the unique element" in a list where everything else appears twice (or three times). That is XOR. Full stop.
"O(1) extra space" combined with integers in a known range. Bit operations are often required, not optional. The constraint is the hint.
"All subsets" or "all combinations of n boolean flags." A bitmask built with OR lets you represent state as a single integer, which unlocks the bitmask DP pattern.
See one of these signals, try bits before you try a hash set. The solution is usually shorter, faster, and the interviewer will notice the difference.
Practice recognizing these patterns under time pressure. SpaceComplexity runs live voice interviews that include bit manipulation problems and gives you precise feedback on where your reasoning broke down, before a real interviewer gets the chance.