DSA & Algorithms
Part 3 of 16 · DSA Advanced & Company FavoritesBit Manipulation & Bitmasks
Bit tricks, XOR family, subset bitmasks, and when FAANG asks bit puzzles.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The state is flags or a subset of a small n
Prefer
Operate on bits
XOR cancels pairs. A mask enumerates subsets when n is at most 20.
- n and n-1 drops the lowest 1.
- A left shift builds the bit-k mask.
- The subset loop is O(n 2^n).
Alternative
Use an extra array of booleans
It works and hides the constant-space trick the prompt wants.
- Pairs need a set instead of XOR.
- Power-of-two becomes a division loop.
- n around 20 still looks like exponential search.
Change one bit family at a time
XOR, clear-lowest, then masks.
- 1
Cancel pairs with XOR
a XOR a is 0. a XOR 0 is a. - 2
Clear the lowest 1
n and n-1. - 3
Loop masks when n is small
Each mask is a subset.
Overview
Bit tricks, XOR family, subset bitmasks, and when FAANG asks bit puzzles.
When companies ask this
Recognition cues: XOR unique/missing; count/reverse bits; power of two; subset enum n≤20; "no + operator".
Mental model
Flow
- 1
1. AND, OR, XOR, shifts
- next2. n and n-1 clears lowest 1
- 2
2. n and n-1 clears lowest 1
- next3. x XOR x is 0
- 3
3. x XOR x is 0
- next4. 1 shifted by k
- 4
4. 1 shifted by k
Lesson map
Bit Manipulation & Bitmasks
Bit tricks, XOR family, subset bitmasks, and when FAANG asks bit puzzles.
Architecture. 1. AND, OR, XOR, shifts Ready. 2. n and n-1 clears lowest 1 Ready. 3. x XOR x is 0 Ready. 4. 1 shifted by k Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Ops["1. AND, OR, XOR, shifts Ready"] Low["2. n and n-1 clears lowest 1 Ready"] Xor["3. x XOR x is 0 Ready"] Mask["4. 1 shifted by k Ready"] Ops -->|continues| Low Low -->|continues| Xor Xor -->|continues| Mask
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Popcount O(k); subsets O(n 2^n).
- Pitfalls: signed shifts; 32-bit assumption; off-by-one bit index.
Interviewer traps
LeetCode drill (real problems)
- Number of 1 Bits
- Counting Bits
- Single Number
- Missing Number
- Sum of Two Integers
- Reverse Bits
- Power of Two
- Subsets
- Maximum XOR of Two Numbers in an Array
YouTube
Interview Q&A
Why XOR unique?
Answer
a^a=0 and a^0=a, so when every other value appears exactly twice the pairs cancel and the single value remains.
n&(n-1)?
Answer
Clear lowest set bit.
Power of two?
Answer
n>0 && !(n&(n-1)).
Bitmask DP when?
Answer
n≤20 used-set state.
Two's complement?
Answer
-x = ~x+1.
Counting bits DP?
Answer
dp[i]=dp[i>>1]+(i&1).
JS signed shift?
Answer
Prefer >>> or mask.
Related?
Answer
dp-advanced bitmask; math.