Why bits show up in interviews
Bit tricks look like party tricks until you see where they live in real systems:
permission flags (chmod 755), database bitmap indexes, Bloom filters, feature
flags packed into one integer, network masks, and the bitmask state in DP.
Interviewers reach for them as a fast signal: a candidate who can derive
x & (x - 1) understands two's-complement; one who memorized it doesn't survive
the follow-up.
💡 Visualizing Bitwise Operators: Analogy: Imagine a 32-bit integer as a row of 32 light switches. Each switch can be either OFF (0) or ON (1).
- AND (
&): A circuit where two switches are connected in series. The light turns ON only if both switches are ON.- OR (
|): A circuit where two switches are connected in parallel. The light turns ON if either switch is ON.- XOR (
^): A two-way hallway switch. The light turns ON if the switches are in different positions (one ON, one OFF). If they match, the light remains OFF.
SDE-1: you can set/clear/test a bit and use XOR to cancel pairs. SDE-2: you derive the counting/power-of-two tricks and reach for a bitmask when the state is a small set. SDE-3 / Staff: you turn a "find the odd one out" word problem into an O(1)-space XOR argument and explain the two's-complement edge cases unprompted. Heaviest at Amazon, Microsoft, Nvidia, Qualcomm, Adobe, Bloomberg; the bitmask form recurs at Google and Meta inside hard DP.
The five operators (the alphabet)
| Op | Symbol | Does |
|---|---|---|
| AND | & | 1 only where both bits are 1 — used to mask / test |
| OR | | | 1 where either is 1 — used to set |
| XOR | ^ | 1 where bits differ — used to toggle / cancel |
| NOT | ~ | flips every bit (two's-complement: ~x == -x - 1) |
| Shift | << >> | multiply / divide by powers of two, build masks |
Watch the operators work
Pick an operator and step across the bit-columns — each result bit depends
only on the two bits directly above it. Change a and b, switch between
AND / OR / XOR, and predict the result row before pressing play.
1/10AND of a = 180 and b = 105, one bit-column at a time (bit 7 is most significant, bit 0 least). A result bit is 1 only when BOTH inputs are 1 — the masking / testing operator. Columns are independent, so we just walk left to right.
The identities that win interviews
Memorizing solutions fails on the follow-up; these five derivations compose into almost every bit question:
- XOR cancels pairs:
a ^ a == 0anda ^ 0 == a, and XOR is commutative + associative. So XOR-ing a whole array makes every duplicated value vanish — whatever's left appeared an odd number of times. x & (x - 1)clears the lowest set bit. Subtracting 1 flips the lowest1to0and everything below it to1; AND-ing wipes that run. Loop until zero to count set bits in O(number-of-set-bits) — Brian Kernighan's trick.x & (-x)isolates the lowest set bit (because-x == ~x + 1). Powers Fenwick trees and "lowest differing bit" arguments.- Power of two ⇔ exactly one set bit ⇔
x > 0 and (x & (x - 1)) == 0. - Subsets ↔ integers. A set of
nitems maps to0 .. 2ⁿ - 1; bitiset means "itemichosen." This is the bridge to bitmask DP (see dp-patterns).
def get_bit(x, i): return (x >> i) & 1
def set_bit(x, i): return x | (1 << i)
def clear_bit(x, i): return x & ~(1 << i)
def toggle_bit(x, i): return x ^ (1 << i)
def count_set_bits(x): # Brian Kernighan: loop runs once per set bit
c = 0
while x:
x &= x - 1 # drop the lowest set bit
c += 1
return c
def is_power_of_two(x):
return x > 0 and (x & (x - 1)) == 0
def single_number(nums): # every value appears twice except one
out = 0
for v in nums:
out ^= v # pairs cancel; the loner survives
return out
def iterate_subsets(items): # all 2^n subsets via the integer ↔ subset bridge
n = len(items)
for mask in range(1 << n):
yield [items[i] for i in range(n) if mask & (1 << i)]
// Java — Bit Manipulation Helpers
public static int getBit(int x, int i) { return (x >> i) & 1; }
public static int setBit(int x, int i) { return x | (1 << i); }
public static int clearBit(int x, int i) { return x & ~(1 << i); }
public static int toggleBit(int x, int i) { return x ^ (1 << i); }
public static int countSetBits(int x) { // Brian Kernighan
int c = 0;
while (x != 0) {
x &= x - 1; // drop lowest set bit
c++;
}
return c;
}
public static boolean isPowerOfTwo(int x) {
return x > 0 && (x & (x - 1)) == 0;
}
public static int singleNumber(int[] nums) {
int out = 0;
for (int v : nums) {
out ^= v;
}
return out;
}
// C++ — Bit Manipulation Helpers
#include <vector>
int getBit(int x, int i) { return (x >> i) & 1; }
int setBit(int x, int i) { return x | (1 << i); }
int clearBit(int x, int i) { return x & ~(1 << i); }
int toggleBit(int x, int i) { return x ^ (1 << i); }
int countSetBits(int x) { // Brian Kernighan
int c = 0;
while (x) {
x &= x - 1; // drop lowest set bit
c++;
}
return c;
}
bool isPowerOfTwo(int x) {
return x > 0 && (x & (x - 1)) == 0;
}
int singleNumber(const std::vector<int>& nums) {
int out = 0;
for (int v : nums) {
out ^= v;
}
return out;
}
Think it through like the interview
The "appears twice" version is a one-liner; the "appears three times" version is where interviewers separate memorizers from derivers — XOR alone can't cancel triples.
PROBLEMEvery element appears exactly three times except one, which appears once. Find it in O(n) time and O(1) space.
- 1
Why the XOR trick dies here
“XOR cancels PAIRS. What happens to a value that appears three times?”
- 2
Count per bit position, mod 3
“Forget the numbers as wholes. What is true of each BIT COLUMN across the array?”
unlocks after the stage above - 3
Collapse 32 counters into two integers
“Can I track 'seen once' and 'seen twice' as bitmasks and reset at three?”
unlocks after the stage above
// Java — Single Number II
public int singleNumberII(int[] nums) {
int ones = 0, twos = 0;
for (int v : nums) {
ones = (ones ^ v) & ~twos;
twos = (twos ^ v) & ~ones;
}
return ones;
}
// C++ — Single Number II
#include <vector>
int singleNumberII(const std::vector<int>& nums) {
int ones = 0, twos = 0;
for (int v : nums) {
ones = (ones ^ v) & ~twos;
twos = (twos ^ v) & ~ones;
}
return ones;
}
Python ints are arbitrary precision with no fixed width — there's no natural
32-bit overflow, so ~x is -x-1 and negative numbers have "infinite" leading 1s.
For fixed-width problems (e.g. Sum of Two Integers) mask with & 0xFFFFFFFF and
reinterpret the sign yourself. In Java use >>> for the logical right shift
(zero-fill) vs >> (sign-extending). In C/C++, shifting by ≥ the width or
left-shifting a negative is undefined behaviour — say so; it's a senior signal.
1. What does x & (x - 1) evaluate to?
2. An array has every value twice except one. Best way to find the loner?
Practice — climb the ladder
The skill is reframing a word problem as bit columns or XOR cancellation. Each rung forces that reframing under a new disguise.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up — SDE-1 fluency
set/test bits and basic XOR cancellation- Number of 1 BitsEasy
Kernighan's x & (x-1) loop — count set bits without scanning all 32.
- Single NumberEasy
The canonical XOR-cancels-pairs one-liner.
- Power of TwoEasy
One-set-bit test: x > 0 and (x & (x-1)) == 0.
- Counting BitsEasy
DP over bits: count[i] = count[i >> 1] + (i & 1).
Core — SDE-2 staples
per-bit reasoning and fixed-width arithmetic- Single Number IIMedium
Per-bit count mod 3, then the two-mask O(1) finish.
- Sum of Two IntegersMedium
Add without + : XOR is the sum, AND<<1 is the carry — plus the Python masking gotcha.
- Reverse BitsEasy
Shift-and-OR across 32 positions; the divide-and-conquer speedup is the follow-up.
- Missing NumberEasy
XOR indices against values so every present number cancels.
Stretch — SDE-3 / Staff XOR puzzles
say the discard/invariant argument out loud- Single Number IIIMedium
Two loners: XOR-all, then split the array by any differing bit (x & -x).
Greedy bit-by-bit with a binary trie — bits meet tries.
The AND of a range is the common high-bit prefix — derive why low bits vanish.
- SubsetsMedium
Enumerate 0..2^n-1 — the integer ↔ subset bridge into bitmask DP.