What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

0. Bit Manipulation Foundation & Bitwise Tricks • Invariant Proof & Speed-Run

Theory Context•Bit Manipulation

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Counting the number of set bits (1-bits) in an unsigned integer—known as the Hamming Weight or Population Count (popcount)—is one of the most fundamental operations in systems engineering and computer architecture. The naive approach inspects all 32 bits by repeatedly shifting right (n >>= 1) and checking n & 1, burning 32 clock cycles regardless of whether the integer has one set bit or thirty-two. Brian Kernighan’s Algorithm eliminates all zero bits instantly, running in exactly $k$ cycles where $k$ is the count of active 1-bits.

🏟️ The Analogy: The Domino Knockdown

Imagine a row of standing dominos where only dominos marked with a red sticker represent 1-bits. Instead of walking past all 32 domino positions and checking each one individually, you reach in with a targeted magnetic swipe that always knocks down the lowest standing red domino and leaves all white dominos untouched. The number of swipes is identical to the number of red dominos.

🔑 Why It Works

Why does n & (n - 1) work? In binary arithmetic, subtracting 1 flips the least significant 1-bit to 0, and flips all trailing 0-bits below it to 1 (e.g., ...1000 becomes ...0111). When this result is bitwise ANDed with original n, the lowest set bit and all bits below it become 0, while all higher-order bits remain completely unaffected.

Visual Blueprint & State Transition Model

Bit Manipulation Mental Model Diagram — Figure 1 • Bit Manipulation Core Invariant & State Lifecycle

Core Invariant Specification

XOR of a number with itself is 0; XOR with 0 is the number itself. n & (n - 1) drops the lowest set bit; n & (-n) isolates it. Bit positions are independent — every operation is just a whole-word parallel map.

Boundary Model: Word-Level Parallel Bitwise State Machine

Bit positions are independent channels processed simultaneously in 1 CPU cycle. n & (n - 1) clears lowest set bit; x ^ x = 0 cancels pairs.

Loop Invariant Termination

while n > 0: n &= n - 1 (terminates after K cycles, K = set bits); or O(1) bitwise expressions.

The 4 Mental Models of Bit Manipulation

Most interview problems are not random tricks: each one repeats a mental model below. Name it before writing code.

1XOR Cancel

stream of numbers ➔ one accumulator ➔ the unpaired answer

XOR Trick (Single Number / XOR Partitioning)

Spot it when: Every value appears an even number of times except one or two, or you must find what is missing or extra between two collections, using O(1) extra space.

Mode 1 · XOR Cancel

Python

1	def single_number(nums: list[int]) -> int:
2	"""Single Number: every value appears twice except one.
3	Time: O(N) \| Space: O(1)
4	"""
5	res = 0 # running XOR of every value seen so far
6
7	# 1. Cancel Paired Values:
8	# XOR each value into res; a value that appears twice XORs with itself
9	# and vanishes, so only the value that appears once survives in res.
10	for num in nums:
11	res ^= num
12	return res
13
14	def single_number_iii(nums: list[int]) -> list[int]:
15	"""Single Number III: two values appear once, every other value twice.
16	Time: O(N) \| Space: O(1)
17	"""
18	xor_all = 0 # running XOR of every value; ends as a ^ b (the two singles)
19
20	# 1. Combine All Values:
21	# XOR every value into xor_all; every value that appears twice cancels,
22	# leaving a ^ b for the two values that each appear once.
23	for num in nums:
24	xor_all ^= num
25
26	# 2. Find a Distinguishing Bit:
27	# a and b differ in every bit that is set in xor_all; keep only the
28	# lowest such bit so the next step can split numbers into two groups by it.
29	diff_bit = xor_all & (-xor_all)
30
31	a, b = 0, 0 # accumulators for each group; each ends holding one of a, b
32
33	# 3. Split and Cancel Within Each Group:
34	# Every value with the bit set is grouped into a (duplicates among them
35	# still cancel there); every value without it is grouped into b the same way.
36	for num in nums:
37	if num & diff_bit:
38	a ^= num
39	else:
40	b ^= num
41
42	return [a, b]

Feed every number through res ^= num. Because x ^ x = 0 and x ^ 0 = x, and XOR does not care about order, every value that appears an even number of times cancels; the accumulator is left holding the value that appeared an odd number of times. The trap is the starting value: res = 0 is right because 0 is the one value XOR leaves unchanged; starting at res = nums[0] while the loop still visits every number XORs nums[0] in twice, so it cancels itself.

Gotchas1 of 4

The trap
Gotcha 1: Starting at res = nums[0] instead of res = 0
Mistake
```
res = nums[0]
```
Fix
```
res = 0
```
What happens: The loop XORs every number into res, nums[0] included. Starting at nums[0] XORs it in a second time. Two copies cancel, so nums[0] disappears from res. res = 0 is the right start, because x ^ 0 = x.
Example: nums = [4, 1, 2, 1, 2]
Mistake: returns 0Fix: returns 4
Gotcha 2: Using XOR when duplicates appear three times
Mistake
```
return single_number(nums)
```
Fix
```
return single_number_ii(nums)
```
What happens: XOR removes a value only when it appears an even number of times. In Single Number II (LC 137), each duplicate appears three times. Three copies XOR to one copy, so the duplicates stay in res. Count each bit instead, as the Per-Bit Counting card does in single_number_ii.
Example: Single Number II (LC 137): nums = [2, 2, 3, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Using xor_all & (xor_all - 1) as the split bit
Mistake
```
diff_bit = xor_all & (xor_all - 1)
```
Fix
```
diff_bit = xor_all & (-xor_all)
```
What happens: In Single Number III (LC 260), xor_all is a ^ b, so each set bit is a place where a and b differ. xor_all & (-xor_all) keeps only the lowest set bit. xor_all & (xor_all - 1) removes that bit instead. When xor_all has one set bit, the result is 0, and every number goes to b. In C++, negating INT_MIN is undefined behavior, so compute diff_bit on an unsigned copy there.
Example: Single Number III (LC 260): nums = [1, 1, 2, 6]
Mistake: returns [0, 4]Fix: returns [6, 2]
Gotcha 4: Testing num & diff_bit == 1
Mistake
```
if num & diff_bit == 1:
```
Fix
```
if num & diff_bit:
```
What happens: num & diff_bit is either 0 or diff_bit itself. It equals 1 only when diff_bit is 1. For any other diff_bit, the test == 1 is always False, and every number goes to b.
Example: nums = [1, 2, 1, 3, 2, 5]
Mistake: returns [0, 6]Fix: returns [3, 5]

Canonical LeetCode:Single Number (LC 136)Find the Difference (LC 389)Single Number III (LC 260)Decode XORed Array (LC 1720)Set Mismatch (LC 645)Missing Number (LC 268)

Open the XOR Cancel card

2Kernighan's Bit Trick

number ➔ lowest set bit ➔ one fewer bit

Brian Kernighan's Algorithm / Popcount (`n & (n-1)`)

Spot it when: The problem counts 1 bits, asks whether a number is a power of two (or four), or needs to visit only the set bits of a mask.

Mode 2 · Kernighan's Bit Trick

Python

1	def count_set_bits(n: int) -> int:
2	"""Number of 1 Bits: counts the 1s with Brian Kernighan's trick.
3	Time: O(K), K = number of set bits (<= 32) \| Space: O(1)
4	"""
5	count = 0
6	while n > 0:
7	n &= (n - 1) # Clear lowest set bit
8	count += 1
9	return count
10
11	def is_power_of_two(n: int) -> bool:
12	"""Power of Two: exactly one set bit, and n must be positive.
13	Time: O(1) \| Space: O(1)
14	"""
15	return n > 0 and (n & (n - 1)) == 0 # n > 0 is mandatory: 0 & -1 == 0

n & (n - 1) clears the lowest set bit of n, so count_set_bits repeats it and counts the rounds until n is 0. Subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1, while the higher bits stay the same, so the AND keeps exactly the higher bits: each round removes one set bit, and the loop runs once per set bit. The same fact makes is_power_of_two one test, since a power of two has exactly one set bit. The trap is n = 0: while n > 0 stops there because no set bit is left to clear, but 0 & -1 is also 0, so is_power_of_two needs the same n > 0 guard, or is_power_of_two(0) returns True.

Gotchas1 of 3

The trap
Gotcha 1: Testing a power of two without n > 0
Mistake
```
return (n & (n - 1)) == 0
```
Fix
```
return n > 0 and (n & (n - 1)) == 0
```
What happens: A power of two has exactly one set bit, so n & (n - 1) clears it and leaves 0. But 0 has no set bit, and 0 & -1 is also 0. So the test alone calls 0 a power of two. The guard n > 0 rules it out.
Example: n = 0
Mistake: returns TrueFix: returns False
Gotcha 2: Shifting with n >>= 1 but counting every round
Mistake
```
n >>= 1
```
Fix
```
n &= (n - 1)
```
What happens: n >>= 1 removes the lowest bit whether it is 1 or 0. The loop still adds 1 to count on every round. So it counts the length of n in bits, not its 1 bits. n &= (n - 1) removes exactly one set bit per round.
Example: n = 11 (binary 1011)
Mistake: returns 4Fix: returns 3
Gotcha 3: Passing a negative n without the 32-bit mask
Mistake
```
count_set_bits(n)
```
Fix
```
count_set_bits(n & 0xFFFFFFFF)
```
What happens: Some problems give a 32-bit value as a signed int, so it can be negative. A negative Python int has no fixed width. while n > 0 then stops at once and returns 0. n & 0xFFFFFFFF keeps the 32 bits the problem means.
Example: n = -1 (32 set bits)
Mistake: returns 0Fix: returns 32

Canonical LeetCode:Number of 1 Bits (LC 191)Counting Bits (LC 338)Prime Number of Set Bits in Binary Representation (LC 762)Power of Four (LC 342)Sort Integers by The Number of 1 Bits (LC 1356)Power of Two (LC 231)Hamming Distance (LC 461)K-th Symbol in Grammar (LC 779)

Open the Kernighan's Bit Trick card

3Bit Tricks

word ➔ masks + shifts ➔ rearranged word

Bit Reversal with Shifts and Masks (Reverse Bits)

Spot it when: The statement asks you to rearrange the bits of one fixed-width number: mirror the bits, or flip them with a mask.

Mode 3 · Bit Tricks

Python

1	def reverse_bits(n: int) -> int:
2	"""Reverse Bits: mirrors the 32 bits of `n`.
3	Time: O(1) (32 iterations) \| Space: O(1)
4	"""
5	res = 0
6	for _ in range(32):
7	res = (res << 1) \| (n & 1) # Shift result left, append n's lowest bit
8	n >>= 1 # Consume that bit from n
9	return res

Treat the number as a fixed row of 32 bits and move bits with shifts and masks, never by converting it to a string. reverse_bits peels the lowest bit off n with n & 1 and appends it to res with res << 1. Each round shifts every bit already in res one place up and drops n's next-lowest bit into the free slot, so after 32 rounds bit i of n sits at bit 31 - i of res. The trap is stopping when n reaches 0: n = 2 would return 1 instead of 1073741824, because the 30 leading zeros of n were never shifted in.

Gotchas1 of 4

The trap
Gotcha 1: Stopping when n reaches 0 with while n:
Mistake
```
while n:
```
Fix
```
for _ in range(32):
```
What happens: Python ints have no fixed width, so the loop must count the 32 bits itself. while n: stops when the last 1 bit of n is read. The leading zeros of n are then never shifted into res. Each of them should move res one place to the left.
Example: n = 2
Mistake: returns 1Fix: returns 1073741824
Gotcha 2: Shifting res after adding the bit
Mistake
```
res = (res | (n & 1)) << 1
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: Each round must first make room at bit 0, then put the new bit there. Shifting after adding moves every bit one place too far. After 32 rounds, res is twice the right answer, so it can need 33 bits.
Example: n = 1
Mistake: returns 4294967296Fix: returns 2147483648
Gotcha 3: Appending n instead of its lowest bit n & 1
Mistake
```
res = (res << 1) | n
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: res must receive one bit per round. (res << 1) | n puts every remaining bit of n into res at once. The bits of n then land in the wrong places, several times over.
Example: n = 2
Mistake: returns 5368709120Fix: returns 1073741824
Gotcha 4: Not shifting n right after each round
Mistake
```
res = (res << 1) | (n & 1)
```
Fix
```
res = (res << 1) | (n & 1)
n >>= 1
```
What happens: n & 1 always reads bit 0 of n. n >>= 1 moves the next bit of n into bit 0 for the next round. Without it, every round reads the same bit, and res gets 32 copies of it.
Example: n = 2
Mistake: returns 0Fix: returns 1073741824

Canonical LeetCode:Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)Number Complement (LC 476)

Open the Bit Tricks card

4Bitmask Subsets

collection ➔ integer mask ➔ subset states

Bitmask Enumeration (Subset Masks)

Spot it when: n is small (roughly 20 or less) and you must try every subset, or a DP state is 'which items are used so far'.

Mode 4 · Bitmask Subsets

Python

1	def read_binary_watch(turnedOn: int) -> list[str]:
2	"""Binary Watch: every set of lit LEDs is one 10-bit mask.
3	Time: O(B * 2^B), B = 10 LEDs \| Space: O(1) extra, output not counted
4	"""
5	times: list[str] = [] # valid "h:mm" strings found so far
6
7	# 1. Visit Every Possible Mask:
8	# Each integer 0 to 2^10 - 1 is one assignment of the 10 LEDs (4 hour bits,
9	# 6 minute bits), so looping over that range visits every combination once.
10	for mask in range(1 << 10):
11	if bin(mask).count("1") != turnedOn: # Popcount: how many LEDs are lit
12	continue
13	hour, minute = mask >> 6, mask & 0b111111 # Top 4 bits: hour; low 6 bits: minute
14
15	# 2. Reject Out-Of-Range Fields:
16	# 4 bits can hold values up to 15 and 6 bits up to 63, but a watch only
17	# shows hours 0-11 and minutes 0-59, so a decoded field outside that range is dropped.
18	if hour < 12 and minute < 60:
19	times.append(f"{hour}:{minute:02d}")
20	return times
21
22
23	def subsets(nums: list[int]) -> list[list[int]]:
24	"""Subsets: every subset of distinct nums, one bitmask per subset.
25	Time: O(N * 2^N) \| Space: O(N * 2^N) output
26	"""
27	n = len(nums)
28	result: list[list[int]] = [] # one subset per mask
29
30	# 1. Decode Each Mask Into Its Subset:
31	# Each integer 0 to 2^n - 1 is one subset; bit i of mask tells whether
32	# nums[i] is included, so collecting the items whose bit is on rebuilds that subset.
33	for mask in range(1 << n):
34	result.append([nums[i] for i in range(n) if (mask >> i) & 1])
35	return result
36
37
38	def enumerate_submasks(mask: int) -> list[int]:
39	"""Sub-Mask Enumeration: every subset of the bits set in `mask`, largest first.
40	Time: O(2^k), k = popcount(mask); O(3^n) summed over all masks \| Space: O(2^k) output
41	"""
42	submasks: list[int] = [] # every non-empty submask found so far, largest first
43	sub = mask
44
45	# 1. Step Through Every Non-Empty Submask:
46	# (sub - 1) & mask clears the lowest set bit of sub and sets every bit below
47	# it, then masking with mask drops anything outside it, landing on the next smaller submask.
48	while sub > 0:
49	submasks.append(sub)
50	sub = (sub - 1) & mask # Drop the lowest bit, keep only bits inside mask
51
52	# 2. Add the Empty Set:
53	# The loop above stops once sub reaches 0, so the empty submask is never
54	# appended inside it; add it once here.
55	submasks.append(0)
56	return submasks

An integer is a set: bit i is on when item i is chosen, so the subsets of n items are exactly the numbers in range(1 << n), (mask >> i) & 1 says whether item i is in, and bin(mask).count("1") how many items are. Each subset matches one number and each number one subset, so one loop visits every subset exactly once, with no recursion and no duplicates; to visit only the subsets of one mask, step with sub = (sub - 1) & mask, which clears the lowest set bit, sets the bits below it, and keeps only bits of mask. The trap is decoding a packed mask: split it into its fields (hour = mask >> 6, minute = mask & 0b111111) and check each field's range (hour < 12 and minute < 60), because 4 bits reach 15 and 6 bits reach 63.

Gotchas1 of 4

The trap
Gotcha 1: Leaving out the check hour < 12 and minute < 60
Mistake
```
times.append(f"{hour}:{minute:02d}")
```
Fix
```
if hour < 12 and minute < 60:
    times.append(f"{hour}:{minute:02d}")
```
What happens: The hour field has 4 bits, so it can hold values up to 15. The minute field has 6 bits, so it can hold values up to 63. A watch shows only hours 0 to 11 and minutes 0 to 59. Without the check, masks such as 15:63 are added as times.
Example: turnedOn = 10
Mistake: returns ['15:63']Fix: returns []
Gotcha 2: Writing the minute without :02d
Mistake
```
times.append(f"{hour}:{minute}")
```
Fix
```
times.append(f"{hour}:{minute:02d}")
```
What happens: Binary Watch (LC 401) writes the minute with two digits, as in "0:01". f"{minute}" writes 1 as "1", so the time becomes "0:1". :02d pads the minute with a zero to two digits.
Example: turnedOn = 1, the first two times
Mistake: returns ['0:1', '0:2']Fix: returns ['0:01', '0:02']
Gotcha 3: Testing bit i + 1 for item i
Mistake
```
result.append([nums[i] for i in range(n) if (mask >> (i + 1)) & 1])
```
Fix
```
result.append([nums[i] for i in range(n) if (mask >> i) & 1])
```
What happens: Bit i of mask stands for nums[i], and bits are numbered from 0. (mask >> (i + 1)) & 1 reads the bit of the next item instead. Item 0 is then never chosen, and some subsets appear twice.
Example: nums = [1, 2]
Mistake: returns [[], [], [1], [1]]Fix: returns [[], [1], [2], [1, 2]]
Gotcha 4: Forgetting the empty set after while sub > 0
Mistake
```
return submasks
```
Fix
```
submasks.append(0)
return submasks
```
What happens: The loop stops as soon as sub reaches 0. So the empty set, sub = 0, is never added inside the loop. submasks.append(0) adds it after the loop.
Example: mask = 0b101
Mistake: returns [5, 4, 1]Fix: returns [5, 4, 1, 0]

Canonical LeetCode:Subsets (LC 78)Binary Watch (LC 401)Count Number of Maximum Bitwise-OR Subsets (LC 2044)Number of Valid Words for Each Puzzle (LC 1178)Generalized Abbreviation (LC 320)Maximum Rows Covered by Columns (LC 2397)

Open the Bitmask Subsets card

Built on the mental models above

Per-Bit CountingPer-Bit Counting (Single Number II / Bitwise State Machine)
A count modulo 3 is kept for each bit, where XOR Cancel keeps one parity bit.
Shared PrefixShared Binary Prefix (Bitwise AND of Numbers Range)
Shift two numbers right together until they are equal, count the shifts in shift, then shift the equal value back left by shift.
Carry AddAdd Without + or - (Sum of Two Integers)
Combine two numbers with XOR and with AND shifted left by 1, then repeat with the carry as the new second number until it is 0.
Gray StepOne-Bit Steps (Gray Code)
Make the code of position i by XOR with i shifted right by 1, so counting up from i to i + 1 changes exactly one bit of the code.

The Bit Manipulation Decision Rule

When facing an unseen bit problem, ask in this order:

Step 1.Are we looking for the one value that appears an odd number of times, or the missing/different element among pairs?

➔ XOR Cancel

Single Number (LC 136)Find the Difference (LC 389)

XOR everything in one pass. If two odd values remain, XOR-all gives a ^ b; use lowbit = xor & -xor to split the array into two buckets and XOR each.

Step 2.Do elements appear a fixed number of times k > 2, or does the answer depend on how many numbers have a 1 in each bit position?

➔ Per-Bit Counting

Single Number II (LC 137)Total Hamming Distance (LC 477)

Count the 1s in each bit position mod k, or keep k-1 registers as a mod-k counter: ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones.

Step 3.Does the input size hint at subsets / states (n <= 12-20), or use words like used/visited/assigned exactly once?

➔ Bitmask Subsets

Subsets (LC 78)Binary Watch (LC 401)

Build an integer mask and index dp[mask] directly; enumerate sub-masks with sub = (sub - 1) & mask.

Step 4.Does the question mention set bits, popcount, power of two, or the lowest bit?

➔ Kernighan's Bit Trick

Number of 1 Bits (LC 191)Counting Bits (LC 338)

Reach for n & (n - 1) or n & -n before any loop over 32 bits.

Step 5.Is the answer the bitwise AND of every integer between two bounds, or the leading bits that two numbers share?

➔ Shared Prefix

Bitwise AND of Numbers Range (LC 201)

Shift both ends right until they are equal, count the shifts in shift, and return left << shift.

Step 6.Must you add two integers without + or -, or repeat an operation until a carry is gone?

➔ Carry Add

Sum of Two Integers (LC 371)Add Binary (LC 67)

total = (a ^ b) & mask, carry = ((a & b) << 1) & mask, then a, b = total, carry until b is 0.

Step 7.Must you list all 2 ** n bit patterns so that neighbouring patterns differ in exactly one bit?

➔ Gray Step

Gray Code (LC 89)Minimum One Bit Operations to Make Integers Zero (LC 1611)

Give position i the code i ^ (i >> 1) for i in range(1 << n); counting from i to i + 1 then changes exactly one bit.

Step 8.Is the problem purely about rearranging or transforming one number's bits (reverse, complement)?

➔ Bit Tricks

Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)

Write the mask-and-shift steps; verify on a small binary example.

Pattern Architecture & Invariant Design Masterclass

Bit manipulation bypasses standard arithmetic loops and directly manipulates the binary representation of integers using single-cycle CPU instructions. It is used to achieve constant-time checks, pack multiple flags into a single integer, and find missing/duplicate elements using bitwise invariants (like XOR).

Every integer is already a sequence of bits. A bitwise operator is a whole-word instruction: one &, |, ^, or shift applies to all 32/64 bits at once, in parallel, in a single cycle. That is why problems that sound like "count", "find the odd one", "toggle", or "enumerate subsets" can jump from O(n) loops or O(n) space to O(1) space and sometimes O(1) time.

The six atomic operations to know cold:

Operation	Symbol	What it does on the bit level	Most common job
AND	`&`	`1` only when both bits are `1`	masking, clearing bits, checking parity, `n & (n-1)`
OR	`\|`	`1` when either bit is `1`	setting bits, merging flags/masks
XOR	`^`	`1` when bits differ	cancellation, toggling, "difference finder"
NOT	`~`	flips every bit (`~x = -x - 1`)	building inverted masks `~(1 << i)`
Left shift	`<<`	moves bits left, fills `0`s	multiply by `2^k`, `1 << i` = bit `i` mask
Right shift	`>>`	moves bits right	divide by `2^k`, extract bit `i` via `(n >> i) & 1`

The identities that make interview solutions possible (memorize these):

x ^ x = 0 and x ^ 0 = x — XOR is its own inverse; pairs cancel.
XOR is commutative and associative — order never matters; a whole stream can be XORed in one pass.
-x = ~x + 1 (two's complement), therefore x & (-x) isolates the lowest set bit.
x & (x - 1) drops the lowest set bit — the engine of popcount and the power-of-two test.
x & (x - 1) == 0 (with x > 0) means x is a power of two (exactly one set bit).
(n >> i) & 1 reads bit i; n | (1 << i) sets it; n & ~(1 << i) clears it; n ^ (1 << i) toggles it.
n & 1 is the parity test (1 = odd). n << k = n * 2^k; n >> k = n // 2^k for non-negative n.

🔬 Variable Anatomy: The 7 Variables Every Bit Manipulation Solution Uses

To connect abstract bitwise logic with concrete Python syntax, here is the universal code anatomy showing what every variable does:

Code / Blueprint

def bitMasterTemplate(nums: list[int], n: int) -> tuple[int, int, int, int, list[int]]:
    # =========================================================================
    # 1. THE BIT ACCUMULATORS & MASK REGISTERS
    # =========================================================================
    xor_acc = 0              # ⚡ XOR Accumulator: cancels paired duplicates (x ^ x = 0)
    ones = 0                 # 1️⃣ Modulo-3 First Residue: bits seen 1 mod 3 times
    twos = 0                 # 2️⃣ Modulo-3 Second Residue: bits seen 2 mod 3 times
    popcount = 0             # 🔢 Set Bit Counter: counts active 1-bits
    subsets_masks = []       # 🎭 Bitmask State Collection: integers representing subsets
 
    # =========================================================================
    # 2. LOWEST-SET-BIT SURGERY & KERNIGHAN'S ENGINE (O(popcount))
    # =========================================================================
    lowbit = n & (-n)        # Isolates the lowest set bit of n (0 when n == 0)
    temp_n = n
    while temp_n > 0:
        # Drops lowest set bit in O(1)
        temp_n &= (temp_n - 1)
        popcount += 1
 
    # =========================================================================
    # 3. PER-BIT STATE MACHINE & SUB-MASK ENUMERATION
    # =========================================================================
    for num in nums:
        # XOR cancellation for single unpaired element
        xor_acc ^= num
        # Modulo-3 finite state machine update
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
 
    # Sub-mask enumeration for an integer mask
    mask = n
    sub = mask
    while sub > 0:
        subsets_masks.append(sub)
        sub = (sub - 1) & mask  # ⚡ Traverses all sub-masks in descending order
 
    return xor_acc, ones, popcount, lowbit, subsets_masks

Variable Role Reference:

Variable	Role in Code	Question It Answers	❌ What Happens If Omitted or Mismanaged?
`n`	Binary integer word	"What raw bit sequence is currently undergoing bitwise surgery?"	❌ In 32-bit signed languages, shifting negative integers without unsigned cast produces arithmetic sign-extension bugs.
`mask`	Integer bitmask filter	"Which specific bit positions am I setting, checking, or toggling?"	❌ Writing `1 << i` with $i \ge 32$ in 32-bit types overflows; in Python, integers grow unboundedly without masking with `0xFFFFFFFF`.
`lowbit`	`n & (-n)`	"What is the isolated lowest power-of-two component?"	❌ Without `lowbit`, isolating the differing bit between two unique XOR elements requires an explicit 32-iteration loop.
`xor_acc`	XOR reduction register	"Which unpaired bit pattern remains after identical pairs cancel to zero?"	❌ Initializing XOR accumulator to anything other than `0` pollutes the cumulative bit parity (`x ^ 0 = x`).
`ones` / `twos`	Mod-3 state registers	"Which bits have appeared $1 \pmod 3$ and $2 \pmod 3$ times?"	❌ Updating `twos` before `ones` with the new value rather than the previous state breaks the finite-state machine cycle.
`carry`	`(a & b) << 1`	"Which bit positions generate an arithmetic carry to the next power?"	❌ In bitwise addition without `+`, forgetting to shift the carry left by 1 fails to add carry bits to higher place values.
`sub`	`(sub - 1) & mask`	"What is the next valid non-empty subset of the active bitmask?"	❌ Using a standard decrement `sub - 1` without `& mask` visits invalid numbers that are not sub-masks of the target.

🧠 The Universal Contract of Bitwise Invariants:

Cancellation Invariant: x ^ x = 0 and x ^ 0 = x. XOR is strictly associative and commutative: order of numbers in a stream never matters.

Lowest Bit Invariants: n & (n - 1) drops the rightmost 1-bit; n & (-n) isolates the rightmost 1-bit.

Whole-Word Invariant: A bitwise instruction executes simultaneously across all 32/64 bit channels in parallel in a single CPU cycle ( $O(1)$ ).

🌟 The 3 Dimensions of Bit Manipulation & The Parallel Word Principle

Every bit manipulation problem is governed by 3 Key Dimensions:

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                     THE 3 DIMENSIONS OF BIT MANIPULATION                    │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. BIT POSITION   │ Parallel 32-bit execution:        │ "Are bit positions  │
│    INDEPENDENCE   │ `&`, `|`, `^`, `~`                │ strictly disjoint?" │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. ALGEBRAIC      │ `x ^ x = 0` (Self-Inverse)        │ "Can paired values  │
│    CANCELLATION   │ Mod-K residue finite state machine│ cancel out cleanly?"│
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. BIT SURGERY &  │ `n & (n-1)` (Drop rightmost 1)    │ "How do we isolate  │
│    MASKING BOUNDS │ `n & (-n)` (Isolate rightmost 1)  │ or iterate bits?"   │
└───────────────────┴───────────────────────────────────┴─────────────────────┘

How this plays out in actual problems:

🟢 Scenario A: XOR Cancellation (Single Number LC 136)

When every element appears twice except one, naive tracking requires an $O(N)$ hash set with $O(N)$ space.
The Rule: XOR every number into accumulator res ^= num. Paired elements cancel to 0 in any order ( $a \oplus b \oplus a = b$ ).
The Result: Finds the odd element in $O(N)$ time with $O(1)$ auxiliary space.

🔵 Scenario B: Lowest-Set-Bit Popcount (Hamming Weight LC 191)

Counting 1-bits with a loop checks all 32 positions every time.
The Rule: Use Brian Kernighan's algorithm n &= (n - 1). Each step subtracts 1 (flipping the lowest 1 to 0 and trailing 0s to 1s) and ANDs with n, obliterating exactly one 1-bit per loop.
The Result: Loop runs exactly $K$ times (where $K$ is the number of 1-bits), never 32.

🟣 Scenario C: Sub-Mask Enumeration (Subset Exhaustion)

Given a bitmask representing a set of features, finding all valid subsets naively tests all $2^N$ integers.
The Rule: Initialize sub = mask. Repeatedly update sub = (sub - 1) & mask until sub == 0.
The Result: Visited states are guaranteed to be exact subsets of mask, running in $O(2^k)$ where $k$ is the number of set bits.

💡 The Ultimate Takeaway Decision Rule:
When analyzing an integer or parity problem, ask: "Is there pair cancellation, bit counting, or subset state packing?"

If Unpaired / Missing element ➔ XOR Accumulation ( $O(N)$ time, $O(1)$ space).

If Counting 1-bits or Power of 2 ➔ n & (n - 1) or n & (-n) surgery.

If Small state space ( $N \le 20$ ) ➔ Integer bitmask representation with 1 << i.

If 3-repeat occurrences ➔ Mod-3 state machine with ones and twos.

🎯 The 5 Essential Bit Manipulation Paradigms & Archetypes

Code / Blueprint

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   THE 5 CORE BIT MANIPULATION ARCHETYPES                                         │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ Core Operation       │ Algebraic Invariant           │ Target Problems & Complexity     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. XOR Cancellation    │ `res ^= num`         │ `x ^ x = 0`, `x ^ 0 = x`      │ Single Number (LC 136), Missing  │
│    (Accumulation)      │ `lowbit = diff&-diff`│ Commutative & Associative     │ Number (LC 268) — O(N), O(1)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Lowest-Bit Surgery  │ `n &= (n - 1)`       │ `n & (n - 1)` clears low bit; │ Hamming Weight (LC 191), Power   │
│    (Popcount / Lowbit) │ `lowbit = n & -n`    │ `n & -n` isolates low bit     │ of Two (LC 231) — O(k), O(1)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. Masks & Sub-Masks   │ `1 << i`,            │ `(n >> i) & 1` tests bit i;   │ Subsets (LC 78), Partition to K  │
│    (Subset Packing)    │ `(sub - 1) & mask`   │ `(sub - 1) & mask` steps sub  │ Equal Subsets (LC 698) — O(2^N)  │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Mod-K State Machine │ `ones = (ones^x)&~two│ Bit registers track counts    │ Single Number II (LC 137) —      │
│    (Residue Counters)  │ `twos = (twos^x)&~one│ modulo K in O(1) space        │ O(N) time, O(1) space            │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 5. Whole-Word Arith.   │ `(a & b) << 1`       │ Fixed mask & shift steps      │ Reverse Bits (LC 190), Sum of    │
│    (Bit Re-arrangement)│ `a ^ b` (half-adder) │ replaces multi-step loops     │ Two Integers (LC 371) — O(1)     │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘

⚡ 1. XOR Cancellation & Bucket Splitting (LC 136 & 260)

Mental Model: XOR cancels duplicate pairs. When two unique elements remain, total_xor = a ^ b. Isolate any differing bit with diff_bit = total_xor & -total_xor to partition all numbers into two disjoint buckets and solve each independently in $O(1)$ space!
Code: see the XOR Cancel card.

✂️ 2. Lowest-Set-Bit Surgery & Popcount (LC 191 & 231)

Mental Model: n & (n - 1) drops the lowest 1-bit; n & (-n) isolates it as a power of 2. A positive number n is a power of 2 if and only if n & (n - 1) == 0.
Code: see the Kernighan's Bit Trick card.

🎭 3. Masks & Sub-Mask Enumeration (LC 78 & 401)

Mental Model: An integer is a packed set of 32 booleans.
Code: see the Bitmask Subsets card.

🔄 4. Per-Bit Mod-K Finite State Machines (LC 137)

Mental Model: When elements appear 3 times and one appears once, XOR alone cannot cancel triples. Maintain two bit registers ones and twos where transitions reset to 0 upon the third occurrence.
Code: see the Per-Bit Counting card.

➕ 5. Whole-Word Arithmetic & Bit Re-arrangement (LC 190 & 371)

Mental Model: Full-adder simulation using a ^ b for sum without carry and (a & b) << 1 for carry propagation until carry becomes 0.
Code Blueprint:

Code / Blueprint

def getSum(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    while b:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK  # keep both inside 32 bits every round
    return a if a <= MAX_INT else ~(a ^ MASK)

🌳 Evaluating Bitwise Invariants & Low-Level State Machines

Understanding the behavior of two's complement and fixed bit widths is vital in interviews:

1. Two's Complement & Sign Extension

In two's complement arithmetic, -x = ~x + 1. This mathematical identity is why x & (-x) precisely isolates the lowest set bit.
In Python, integers have arbitrary precision and do not overflow to 32-bit negatives. To simulate 32-bit signed integers, mask with 0xFFFFFFFF and convert values exceeding 0x7FFFFFFF using ~(val ^ 0xFFFFFFFF).

2. Constant Time Complexity Invariants

Operating on 32-bit words takes strictly $O(1)$ time and $O(1)$ space.
Sub-mask iteration sub = (sub - 1) & mask takes total time $\sum_{k=0}^N \binom{N}{k} 2^k = 3^N$ , which is significantly faster than checking all pairs $4^N$ .

💡 Staff SWE Architectural Invariant:
Bitwise operations treat the integer word as a SIMD register of 32 or 64 independent parallel 1-bit execution units. When you can express logic with &, |, ^, and shifts, you eliminate branch mispredictions and achieve optimal single-cycle throughput.

Understanding Invariants: XOR Cancellation & Lowest-Bit Surgery

XOR of a number with itself is 0; XOR with 0 is the number itself. n & (n - 1) drops the lowest set bit; n & (-n) isolates it. Bit positions are independent — every operation is just a whole-word parallel map.

A bitwise operator is a whole-word instruction applying to all 32/64 bits in parallel in a single cycle. Algebraic cancellations turn quadratic scans into O(N) single passes with O(1) memory.

Lowest-Set-Bit Kernighan Invariant

Condition: While n > 0, execute n &= (n - 1)

Action: drops rightmost 1-bit in O(1) time without looping over all 32 bits

Subtracting 1 flips trailing zeros to 1s and the lowest 1 to 0; ANDing with n zeroes out the lowest set bit.

XOR Algebraic Cancellation Invariant

Condition: For any sequence where duplicates appear an even number of times

Action: accumulate stream with res ^= x

Because x ^ x = 0 and x ^ 0 = x, all paired entries annihilate to 0 regardless of order, leaving the lone odd element.

Common Questions

"In Single Number, why does XORing every element together leave just the one that appears once — doesn't the order the elements arrive in matter?"

It doesn't, and that's exactly the property that makes the one-line solution work: XOR is both its own inverse and commutative/associative, so pairs cancel regardless of where they sit in the array.

Every value that appears twice contributes x ^ x, which is 0 — the pair contributes nothing to the running result, no matter how far apart the two copies are or what's XORed in between them. Because XOR is commutative and associative, you can reorder the whole expression as if every pair were sitting right next to each other, even though they aren't in the actual array. What survives after every pair cancels is 0 ^ unique_value, which — by the other half of the identity, x ^ 0 = x — is just unique_value itself.

This is why a single for num in nums: res ^= num pass, in O(1) extra space, finds the unpaired element without ever building a frequency map: you're not counting occurrences at all, you're relying on pairs annihilating each other bit-by-bit, in parallel, across all 32/64 bits at once. It's also exactly why this trick needs adapting for harder variants: when duplicates appear three times instead of two (Single Number II), x ^ x ^ x = x survives instead of cancelling, so plain XOR is replaced by a mod-3 bit-counting state machine (ones/twos registers) instead. When there are two distinct unique values hiding among pairs (Single Number III), XORing everything together doesn't isolate either one — it gives their XOR — so the fix is different again: XOR everything first, take any set bit in that result (lowbit = xor & -xor) to find one position where the two uniques differ, and split the whole array into two groups by that bit; plain pairwise cancellation now finds one unique value per group.

Coach discussion points

1.
Why does n & (n - 1) clear the lowest set bit? Discuss the cascade of carries in n - 1.
2.
In Single Number II, how do ones and twos track modulo 3 logic without an array? What would a fourth register do?
3.
Contrast logical shift (>>>) vs arithmetic shift (>>) in Java/JS. Why does Python not have this issue, and how do you simulate 32-bit bounds in Python?
4.
Why is x ^ y a valid "difference detector" for Hamming distance? How does (x ^ y) turn into a count?
5.
When would plain XOR fail (e.g. "appears three times"), and why does splitting by lowbit = xor & -xor rescue Single Number III but not Single Number II?
6.
How does sub = (sub - 1) & mask visit every sub-mask exactly once? Prove it terminates and never revisits.
7.
When the constraint says n <= 20, which families become available, and what is the time/space cost of enumerating all 2^n masks?
8.
In Maximum XOR of Two Numbers, why must the mask grow strictly from MSB to LSB rather than any other order? What invariant breaks if you process bits LSB-first?
9.
Prove that max_xor never decreases across iterations, and that every bit it locks in was already proven achievable by two real numbers. Why does this guarantee optimality without ever comparing all $O(N^2)$ pairs?
10.
Contrast the hash-set prefix implementation with a classical bit-trie implementation of the same algorithm. What does the trie make explicit that the hash-set version hides, and when would the trie's O(N) (amortized) walk beat the hash-set's O(N) rebuild-per-bit?

Complexity analysis

Time Complexity:
- $O(1)$ for operations bounding to a fixed 32 or 64 bits (e.g. Reverse Bits).
- $O(k)$ where $k$ is the number of set bits (Brian Kernighan's).
- $O(N)$ for Single Number (iterating over the array).
Space Complexity: $O(1)$ auxiliary space for almost all pure bit manipulation problems.

Production Systems Deployment & Motivation

In high-performance networking and database systems, flags are stored as bits in a single 32-bit or 64-bit integer to save space and minimize cache misses. Determining if a specific feature is enabled takes a single bitwise AND operation, rather than iterating through a list of booleans. Bit manipulation is also foundational for IP subnet masking, hashing algorithms, and parity-based error detection.

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if bitwise identities and binary masking feel low-level right now! Bit manipulation replaces arithmetic loops with single-cycle CPU instructions that process entire 32/64-bit words in parallel. As you progress through the Archetype Variants (from Hamming Weight and Single Number to Bit State Machines and Bitmask Subsets), each hands-on challenge will cement this intuition until wielding n & (n - 1), n & (-n), and XOR cancellation becomes second nature.

Iterating 32 times instead of using Brian Kernighan's algorithm: Checking all 32 bits with n >>= 1 always takes 32 iterations. Using n &= (n - 1) clears the lowest set bit in each step, executing in operations strictly proportional to the number of set bits.
Signed vs unsigned right shift: In Java, C++, and C#, using signed right shift >> on negative integers propagates the sign bit (1s), causing infinite loops. Always use unsigned right shift >>> or cast to unsigned.
Bitwise operator precedence: Bitwise operators (&, |, ^) have lower precedence than comparison operators (==, !=). Writing n & 1 == 1 evaluates 1 == 1 first, resulting in n & True.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "single number among duplicates", "count set bits / Hamming weight", "subsets via binary mask", "power of two check". Exploits direct hardware-level ALU bitwise operations (&, |, ^, ~, <<, >>).

CONSTRAINTS & BOUNDS

Bit-width $W \in \{32, 64\}$ . All primitive bitwise operations execute in a single CPU clock cycle ( $O(1)$ hardware instructions). Enables processing subsets of size $N \le 32$ or $N \le 64$ inside a single register.

FAANG PRODUCTION TRAPS & EDGE CASES

Operator precedence bugs in languages like C++/Java/Python where arithmetic + has higher precedence than bitwise << or & (always use explicit parentheses: (x & 1)); signed shift overflow on negative integers (use unsigned shift >>> where applicable).

Theory Context•Bit Manipulation

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Domino Knockdown

🔑 Why It Works

Visual Blueprint & State Transition Model

Core Invariant Specification

Boundary Model: Word-Level Parallel Bitwise State Machine

Bit positions are independent channels processed simultaneously in 1 CPU cycle. n & (n - 1) clears lowest set bit; x ^ x = 0 cancels pairs.

Loop Invariant Termination

while n > 0: n &= n - 1 (terminates after K cycles, K = set bits); or O(1) bitwise expressions.

The 4 Mental Models of Bit Manipulation

Most interview problems are not random tricks: each one repeats a mental model below. Name it before writing code.

1XOR Cancel

stream of numbers ➔ one accumulator ➔ the unpaired answer

XOR Trick (Single Number / XOR Partitioning)

Spot it when: Every value appears an even number of times except one or two, or you must find what is missing or extra between two collections, using O(1) extra space.

Mode 1 · XOR Cancel

Python

1	def single_number(nums: list[int]) -> int:
2	"""Single Number: every value appears twice except one.
3	Time: O(N) \| Space: O(1)
4	"""
5	res = 0 # running XOR of every value seen so far
6
7	# 1. Cancel Paired Values:
8	# XOR each value into res; a value that appears twice XORs with itself
9	# and vanishes, so only the value that appears once survives in res.
10	for num in nums:
11	res ^= num
12	return res
13
14	def single_number_iii(nums: list[int]) -> list[int]:
15	"""Single Number III: two values appear once, every other value twice.
16	Time: O(N) \| Space: O(1)
17	"""
18	xor_all = 0 # running XOR of every value; ends as a ^ b (the two singles)
19
20	# 1. Combine All Values:
21	# XOR every value into xor_all; every value that appears twice cancels,
22	# leaving a ^ b for the two values that each appear once.
23	for num in nums:
24	xor_all ^= num
25
26	# 2. Find a Distinguishing Bit:
27	# a and b differ in every bit that is set in xor_all; keep only the
28	# lowest such bit so the next step can split numbers into two groups by it.
29	diff_bit = xor_all & (-xor_all)
30
31	a, b = 0, 0 # accumulators for each group; each ends holding one of a, b
32
33	# 3. Split and Cancel Within Each Group:
34	# Every value with the bit set is grouped into a (duplicates among them
35	# still cancel there); every value without it is grouped into b the same way.
36	for num in nums:
37	if num & diff_bit:
38	a ^= num
39	else:
40	b ^= num
41
42	return [a, b]

Gotchas1 of 4

The trap
Gotcha 1: Starting at res = nums[0] instead of res = 0
Mistake
```
res = nums[0]
```
Fix
```
res = 0
```
What happens: The loop XORs every number into res, nums[0] included. Starting at nums[0] XORs it in a second time. Two copies cancel, so nums[0] disappears from res. res = 0 is the right start, because x ^ 0 = x.
Example: nums = [4, 1, 2, 1, 2]
Mistake: returns 0Fix: returns 4
Gotcha 2: Using XOR when duplicates appear three times
Mistake
```
return single_number(nums)
```
Fix
```
return single_number_ii(nums)
```
What happens: XOR removes a value only when it appears an even number of times. In Single Number II (LC 137), each duplicate appears three times. Three copies XOR to one copy, so the duplicates stay in res. Count each bit instead, as the Per-Bit Counting card does in single_number_ii.
Example: Single Number II (LC 137): nums = [2, 2, 3, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Using xor_all & (xor_all - 1) as the split bit
Mistake
```
diff_bit = xor_all & (xor_all - 1)
```
Fix
```
diff_bit = xor_all & (-xor_all)
```
What happens: In Single Number III (LC 260), xor_all is a ^ b, so each set bit is a place where a and b differ. xor_all & (-xor_all) keeps only the lowest set bit. xor_all & (xor_all - 1) removes that bit instead. When xor_all has one set bit, the result is 0, and every number goes to b. In C++, negating INT_MIN is undefined behavior, so compute diff_bit on an unsigned copy there.
Example: Single Number III (LC 260): nums = [1, 1, 2, 6]
Mistake: returns [0, 4]Fix: returns [6, 2]
Gotcha 4: Testing num & diff_bit == 1
Mistake
```
if num & diff_bit == 1:
```
Fix
```
if num & diff_bit:
```
What happens: num & diff_bit is either 0 or diff_bit itself. It equals 1 only when diff_bit is 1. For any other diff_bit, the test == 1 is always False, and every number goes to b.
Example: nums = [1, 2, 1, 3, 2, 5]
Mistake: returns [0, 6]Fix: returns [3, 5]

Canonical LeetCode:Single Number (LC 136)Find the Difference (LC 389)Single Number III (LC 260)Decode XORed Array (LC 1720)Set Mismatch (LC 645)Missing Number (LC 268)

Open the XOR Cancel card

2Kernighan's Bit Trick

number ➔ lowest set bit ➔ one fewer bit

Brian Kernighan's Algorithm / Popcount (`n & (n-1)`)

Spot it when: The problem counts 1 bits, asks whether a number is a power of two (or four), or needs to visit only the set bits of a mask.

Mode 2 · Kernighan's Bit Trick

Python

1	def count_set_bits(n: int) -> int:
2	"""Number of 1 Bits: counts the 1s with Brian Kernighan's trick.
3	Time: O(K), K = number of set bits (<= 32) \| Space: O(1)
4	"""
5	count = 0
6	while n > 0:
7	n &= (n - 1) # Clear lowest set bit
8	count += 1
9	return count
10
11	def is_power_of_two(n: int) -> bool:
12	"""Power of Two: exactly one set bit, and n must be positive.
13	Time: O(1) \| Space: O(1)
14	"""
15	return n > 0 and (n & (n - 1)) == 0 # n > 0 is mandatory: 0 & -1 == 0

Gotchas1 of 3

The trap
Gotcha 1: Testing a power of two without n > 0
Mistake
```
return (n & (n - 1)) == 0
```
Fix
```
return n > 0 and (n & (n - 1)) == 0
```
What happens: A power of two has exactly one set bit, so n & (n - 1) clears it and leaves 0. But 0 has no set bit, and 0 & -1 is also 0. So the test alone calls 0 a power of two. The guard n > 0 rules it out.
Example: n = 0
Mistake: returns TrueFix: returns False
Gotcha 2: Shifting with n >>= 1 but counting every round
Mistake
```
n >>= 1
```
Fix
```
n &= (n - 1)
```
What happens: n >>= 1 removes the lowest bit whether it is 1 or 0. The loop still adds 1 to count on every round. So it counts the length of n in bits, not its 1 bits. n &= (n - 1) removes exactly one set bit per round.
Example: n = 11 (binary 1011)
Mistake: returns 4Fix: returns 3
Gotcha 3: Passing a negative n without the 32-bit mask
Mistake
```
count_set_bits(n)
```
Fix
```
count_set_bits(n & 0xFFFFFFFF)
```
What happens: Some problems give a 32-bit value as a signed int, so it can be negative. A negative Python int has no fixed width. while n > 0 then stops at once and returns 0. n & 0xFFFFFFFF keeps the 32 bits the problem means.
Example: n = -1 (32 set bits)
Mistake: returns 0Fix: returns 32

Open the Kernighan's Bit Trick card

3Bit Tricks

word ➔ masks + shifts ➔ rearranged word

Bit Reversal with Shifts and Masks (Reverse Bits)

Spot it when: The statement asks you to rearrange the bits of one fixed-width number: mirror the bits, or flip them with a mask.

Mode 3 · Bit Tricks

Python

1	def reverse_bits(n: int) -> int:
2	"""Reverse Bits: mirrors the 32 bits of `n`.
3	Time: O(1) (32 iterations) \| Space: O(1)
4	"""
5	res = 0
6	for _ in range(32):
7	res = (res << 1) \| (n & 1) # Shift result left, append n's lowest bit
8	n >>= 1 # Consume that bit from n
9	return res

Gotchas1 of 4

The trap
Gotcha 1: Stopping when n reaches 0 with while n:
Mistake
```
while n:
```
Fix
```
for _ in range(32):
```
What happens: Python ints have no fixed width, so the loop must count the 32 bits itself. while n: stops when the last 1 bit of n is read. The leading zeros of n are then never shifted into res. Each of them should move res one place to the left.
Example: n = 2
Mistake: returns 1Fix: returns 1073741824
Gotcha 2: Shifting res after adding the bit
Mistake
```
res = (res | (n & 1)) << 1
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: Each round must first make room at bit 0, then put the new bit there. Shifting after adding moves every bit one place too far. After 32 rounds, res is twice the right answer, so it can need 33 bits.
Example: n = 1
Mistake: returns 4294967296Fix: returns 2147483648
Gotcha 3: Appending n instead of its lowest bit n & 1
Mistake
```
res = (res << 1) | n
```
Fix
```
res = (res << 1) | (n & 1)
```
What happens: res must receive one bit per round. (res << 1) | n puts every remaining bit of n into res at once. The bits of n then land in the wrong places, several times over.
Example: n = 2
Mistake: returns 5368709120Fix: returns 1073741824
Gotcha 4: Not shifting n right after each round
Mistake
```
res = (res << 1) | (n & 1)
```
Fix
```
res = (res << 1) | (n & 1)
n >>= 1
```
What happens: n & 1 always reads bit 0 of n. n >>= 1 moves the next bit of n into bit 0 for the next round. Without it, every round reads the same bit, and res gets 32 copies of it.
Example: n = 2
Mistake: returns 0Fix: returns 1073741824

Canonical LeetCode:Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)Number Complement (LC 476)

Open the Bit Tricks card

4Bitmask Subsets

collection ➔ integer mask ➔ subset states

Bitmask Enumeration (Subset Masks)

Spot it when: n is small (roughly 20 or less) and you must try every subset, or a DP state is 'which items are used so far'.

Mode 4 · Bitmask Subsets

Python

1	def read_binary_watch(turnedOn: int) -> list[str]:
2	"""Binary Watch: every set of lit LEDs is one 10-bit mask.
3	Time: O(B * 2^B), B = 10 LEDs \| Space: O(1) extra, output not counted
4	"""
5	times: list[str] = [] # valid "h:mm" strings found so far
6
7	# 1. Visit Every Possible Mask:
8	# Each integer 0 to 2^10 - 1 is one assignment of the 10 LEDs (4 hour bits,
9	# 6 minute bits), so looping over that range visits every combination once.
10	for mask in range(1 << 10):
11	if bin(mask).count("1") != turnedOn: # Popcount: how many LEDs are lit
12	continue
13	hour, minute = mask >> 6, mask & 0b111111 # Top 4 bits: hour; low 6 bits: minute
14
15	# 2. Reject Out-Of-Range Fields:
16	# 4 bits can hold values up to 15 and 6 bits up to 63, but a watch only
17	# shows hours 0-11 and minutes 0-59, so a decoded field outside that range is dropped.
18	if hour < 12 and minute < 60:
19	times.append(f"{hour}:{minute:02d}")
20	return times
21
22
23	def subsets(nums: list[int]) -> list[list[int]]:
24	"""Subsets: every subset of distinct nums, one bitmask per subset.
25	Time: O(N * 2^N) \| Space: O(N * 2^N) output
26	"""
27	n = len(nums)
28	result: list[list[int]] = [] # one subset per mask
29
30	# 1. Decode Each Mask Into Its Subset:
31	# Each integer 0 to 2^n - 1 is one subset; bit i of mask tells whether
32	# nums[i] is included, so collecting the items whose bit is on rebuilds that subset.
33	for mask in range(1 << n):
34	result.append([nums[i] for i in range(n) if (mask >> i) & 1])
35	return result
36
37
38	def enumerate_submasks(mask: int) -> list[int]:
39	"""Sub-Mask Enumeration: every subset of the bits set in `mask`, largest first.
40	Time: O(2^k), k = popcount(mask); O(3^n) summed over all masks \| Space: O(2^k) output
41	"""
42	submasks: list[int] = [] # every non-empty submask found so far, largest first
43	sub = mask
44
45	# 1. Step Through Every Non-Empty Submask:
46	# (sub - 1) & mask clears the lowest set bit of sub and sets every bit below
47	# it, then masking with mask drops anything outside it, landing on the next smaller submask.
48	while sub > 0:
49	submasks.append(sub)
50	sub = (sub - 1) & mask # Drop the lowest bit, keep only bits inside mask
51
52	# 2. Add the Empty Set:
53	# The loop above stops once sub reaches 0, so the empty submask is never
54	# appended inside it; add it once here.
55	submasks.append(0)
56	return submasks

Gotchas1 of 4

The trap
Gotcha 1: Leaving out the check hour < 12 and minute < 60
Mistake
```
times.append(f"{hour}:{minute:02d}")
```
Fix
```
if hour < 12 and minute < 60:
    times.append(f"{hour}:{minute:02d}")
```
What happens: The hour field has 4 bits, so it can hold values up to 15. The minute field has 6 bits, so it can hold values up to 63. A watch shows only hours 0 to 11 and minutes 0 to 59. Without the check, masks such as 15:63 are added as times.
Example: turnedOn = 10
Mistake: returns ['15:63']Fix: returns []
Gotcha 2: Writing the minute without :02d
Mistake
```
times.append(f"{hour}:{minute}")
```
Fix
```
times.append(f"{hour}:{minute:02d}")
```
What happens: Binary Watch (LC 401) writes the minute with two digits, as in "0:01". f"{minute}" writes 1 as "1", so the time becomes "0:1". :02d pads the minute with a zero to two digits.
Example: turnedOn = 1, the first two times
Mistake: returns ['0:1', '0:2']Fix: returns ['0:01', '0:02']
Gotcha 3: Testing bit i + 1 for item i
Mistake
```
result.append([nums[i] for i in range(n) if (mask >> (i + 1)) & 1])
```
Fix
```
result.append([nums[i] for i in range(n) if (mask >> i) & 1])
```
What happens: Bit i of mask stands for nums[i], and bits are numbered from 0. (mask >> (i + 1)) & 1 reads the bit of the next item instead. Item 0 is then never chosen, and some subsets appear twice.
Example: nums = [1, 2]
Mistake: returns [[], [], [1], [1]]Fix: returns [[], [1], [2], [1, 2]]
Gotcha 4: Forgetting the empty set after while sub > 0
Mistake
```
return submasks
```
Fix
```
submasks.append(0)
return submasks
```
What happens: The loop stops as soon as sub reaches 0. So the empty set, sub = 0, is never added inside the loop. submasks.append(0) adds it after the loop.
Example: mask = 0b101
Mistake: returns [5, 4, 1]Fix: returns [5, 4, 1, 0]

Open the Bitmask Subsets card

Built on the mental models above

Per-Bit CountingPer-Bit Counting (Single Number II / Bitwise State Machine)
A count modulo 3 is kept for each bit, where XOR Cancel keeps one parity bit.
Shared PrefixShared Binary Prefix (Bitwise AND of Numbers Range)
Shift two numbers right together until they are equal, count the shifts in shift, then shift the equal value back left by shift.
Carry AddAdd Without + or - (Sum of Two Integers)
Combine two numbers with XOR and with AND shifted left by 1, then repeat with the carry as the new second number until it is 0.
Gray StepOne-Bit Steps (Gray Code)
Make the code of position i by XOR with i shifted right by 1, so counting up from i to i + 1 changes exactly one bit of the code.

The Bit Manipulation Decision Rule

When facing an unseen bit problem, ask in this order:

Step 1.Are we looking for the one value that appears an odd number of times, or the missing/different element among pairs?

➔ XOR Cancel

Single Number (LC 136)Find the Difference (LC 389)

XOR everything in one pass. If two odd values remain, XOR-all gives a ^ b; use lowbit = xor & -xor to split the array into two buckets and XOR each.

Step 2.Do elements appear a fixed number of times k > 2, or does the answer depend on how many numbers have a 1 in each bit position?

➔ Per-Bit Counting

Single Number II (LC 137)Total Hamming Distance (LC 477)

Count the 1s in each bit position mod k, or keep k-1 registers as a mod-k counter: ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones.

Step 3.Does the input size hint at subsets / states (n <= 12-20), or use words like used/visited/assigned exactly once?

➔ Bitmask Subsets

Subsets (LC 78)Binary Watch (LC 401)

Build an integer mask and index dp[mask] directly; enumerate sub-masks with sub = (sub - 1) & mask.

Step 4.Does the question mention set bits, popcount, power of two, or the lowest bit?

➔ Kernighan's Bit Trick

Number of 1 Bits (LC 191)Counting Bits (LC 338)

Reach for n & (n - 1) or n & -n before any loop over 32 bits.

Step 5.Is the answer the bitwise AND of every integer between two bounds, or the leading bits that two numbers share?

➔ Shared Prefix

Bitwise AND of Numbers Range (LC 201)

Shift both ends right until they are equal, count the shifts in shift, and return left << shift.

Step 6.Must you add two integers without + or -, or repeat an operation until a carry is gone?

➔ Carry Add

Sum of Two Integers (LC 371)Add Binary (LC 67)

total = (a ^ b) & mask, carry = ((a & b) << 1) & mask, then a, b = total, carry until b is 0.

Step 7.Must you list all 2 ** n bit patterns so that neighbouring patterns differ in exactly one bit?

➔ Gray Step

Gray Code (LC 89)Minimum One Bit Operations to Make Integers Zero (LC 1611)

Give position i the code i ^ (i >> 1) for i in range(1 << n); counting from i to i + 1 then changes exactly one bit.

Step 8.Is the problem purely about rearranging or transforming one number's bits (reverse, complement)?

➔ Bit Tricks

Reverse Bits (LC 190)Complement of Base 10 Integer (LC 1009)

Write the mask-and-shift steps; verify on a small binary example.

Pattern Architecture & Invariant Design Masterclass

The six atomic operations to know cold:

Operation	Symbol	What it does on the bit level	Most common job
AND	`&`	`1` only when both bits are `1`	masking, clearing bits, checking parity, `n & (n-1)`
OR	`\|`	`1` when either bit is `1`	setting bits, merging flags/masks
XOR	`^`	`1` when bits differ	cancellation, toggling, "difference finder"
NOT	`~`	flips every bit (`~x = -x - 1`)	building inverted masks `~(1 << i)`
Left shift	`<<`	moves bits left, fills `0`s	multiply by `2^k`, `1 << i` = bit `i` mask
Right shift	`>>`	moves bits right	divide by `2^k`, extract bit `i` via `(n >> i) & 1`

The identities that make interview solutions possible (memorize these):

x ^ x = 0 and x ^ 0 = x — XOR is its own inverse; pairs cancel.
XOR is commutative and associative — order never matters; a whole stream can be XORed in one pass.
-x = ~x + 1 (two's complement), therefore x & (-x) isolates the lowest set bit.
x & (x - 1) drops the lowest set bit — the engine of popcount and the power-of-two test.
x & (x - 1) == 0 (with x > 0) means x is a power of two (exactly one set bit).
(n >> i) & 1 reads bit i; n | (1 << i) sets it; n & ~(1 << i) clears it; n ^ (1 << i) toggles it.
n & 1 is the parity test (1 = odd). n << k = n * 2^k; n >> k = n // 2^k for non-negative n.

🔬 Variable Anatomy: The 7 Variables Every Bit Manipulation Solution Uses

To connect abstract bitwise logic with concrete Python syntax, here is the universal code anatomy showing what every variable does:

Code / Blueprint

def bitMasterTemplate(nums: list[int], n: int) -> tuple[int, int, int, int, list[int]]:
    # =========================================================================
    # 1. THE BIT ACCUMULATORS & MASK REGISTERS
    # =========================================================================
    xor_acc = 0              # ⚡ XOR Accumulator: cancels paired duplicates (x ^ x = 0)
    ones = 0                 # 1️⃣ Modulo-3 First Residue: bits seen 1 mod 3 times
    twos = 0                 # 2️⃣ Modulo-3 Second Residue: bits seen 2 mod 3 times
    popcount = 0             # 🔢 Set Bit Counter: counts active 1-bits
    subsets_masks = []       # 🎭 Bitmask State Collection: integers representing subsets
 
    # =========================================================================
    # 2. LOWEST-SET-BIT SURGERY & KERNIGHAN'S ENGINE (O(popcount))
    # =========================================================================
    lowbit = n & (-n)        # Isolates the lowest set bit of n (0 when n == 0)
    temp_n = n
    while temp_n > 0:
        # Drops lowest set bit in O(1)
        temp_n &= (temp_n - 1)
        popcount += 1
 
    # =========================================================================
    # 3. PER-BIT STATE MACHINE & SUB-MASK ENUMERATION
    # =========================================================================
    for num in nums:
        # XOR cancellation for single unpaired element
        xor_acc ^= num
        # Modulo-3 finite state machine update
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
 
    # Sub-mask enumeration for an integer mask
    mask = n
    sub = mask
    while sub > 0:
        subsets_masks.append(sub)
        sub = (sub - 1) & mask  # ⚡ Traverses all sub-masks in descending order
 
    return xor_acc, ones, popcount, lowbit, subsets_masks

Variable Role Reference:

Variable	Role in Code	Question It Answers	❌ What Happens If Omitted or Mismanaged?
`n`	Binary integer word	"What raw bit sequence is currently undergoing bitwise surgery?"	❌ In 32-bit signed languages, shifting negative integers without unsigned cast produces arithmetic sign-extension bugs.
`mask`	Integer bitmask filter	"Which specific bit positions am I setting, checking, or toggling?"	❌ Writing `1 << i` with $i \ge 32$ in 32-bit types overflows; in Python, integers grow unboundedly without masking with `0xFFFFFFFF`.
`lowbit`	`n & (-n)`	"What is the isolated lowest power-of-two component?"	❌ Without `lowbit`, isolating the differing bit between two unique XOR elements requires an explicit 32-iteration loop.
`xor_acc`	XOR reduction register	"Which unpaired bit pattern remains after identical pairs cancel to zero?"	❌ Initializing XOR accumulator to anything other than `0` pollutes the cumulative bit parity (`x ^ 0 = x`).
`ones` / `twos`	Mod-3 state registers	"Which bits have appeared $1 \pmod 3$ and $2 \pmod 3$ times?"	❌ Updating `twos` before `ones` with the new value rather than the previous state breaks the finite-state machine cycle.
`carry`	`(a & b) << 1`	"Which bit positions generate an arithmetic carry to the next power?"	❌ In bitwise addition without `+`, forgetting to shift the carry left by 1 fails to add carry bits to higher place values.
`sub`	`(sub - 1) & mask`	"What is the next valid non-empty subset of the active bitmask?"	❌ Using a standard decrement `sub - 1` without `& mask` visits invalid numbers that are not sub-masks of the target.

🧠 The Universal Contract of Bitwise Invariants:

Cancellation Invariant: x ^ x = 0 and x ^ 0 = x. XOR is strictly associative and commutative: order of numbers in a stream never matters.

Lowest Bit Invariants: n & (n - 1) drops the rightmost 1-bit; n & (-n) isolates the rightmost 1-bit.

Whole-Word Invariant: A bitwise instruction executes simultaneously across all 32/64 bit channels in parallel in a single CPU cycle ( $O(1)$ ).

🌟 The 3 Dimensions of Bit Manipulation & The Parallel Word Principle

Every bit manipulation problem is governed by 3 Key Dimensions:

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                     THE 3 DIMENSIONS OF BIT MANIPULATION                    │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. BIT POSITION   │ Parallel 32-bit execution:        │ "Are bit positions  │
│    INDEPENDENCE   │ `&`, `|`, `^`, `~`                │ strictly disjoint?" │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. ALGEBRAIC      │ `x ^ x = 0` (Self-Inverse)        │ "Can paired values  │
│    CANCELLATION   │ Mod-K residue finite state machine│ cancel out cleanly?"│
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. BIT SURGERY &  │ `n & (n-1)` (Drop rightmost 1)    │ "How do we isolate  │
│    MASKING BOUNDS │ `n & (-n)` (Isolate rightmost 1)  │ or iterate bits?"   │
└───────────────────┴───────────────────────────────────┴─────────────────────┘

How this plays out in actual problems:

🟢 Scenario A: XOR Cancellation (Single Number LC 136)

When every element appears twice except one, naive tracking requires an $O(N)$ hash set with $O(N)$ space.
The Rule: XOR every number into accumulator res ^= num. Paired elements cancel to 0 in any order ( $a \oplus b \oplus a = b$ ).
The Result: Finds the odd element in $O(N)$ time with $O(1)$ auxiliary space.

🔵 Scenario B: Lowest-Set-Bit Popcount (Hamming Weight LC 191)

Counting 1-bits with a loop checks all 32 positions every time.
The Rule: Use Brian Kernighan's algorithm n &= (n - 1). Each step subtracts 1 (flipping the lowest 1 to 0 and trailing 0s to 1s) and ANDs with n, obliterating exactly one 1-bit per loop.
The Result: Loop runs exactly $K$ times (where $K$ is the number of 1-bits), never 32.

🟣 Scenario C: Sub-Mask Enumeration (Subset Exhaustion)

Given a bitmask representing a set of features, finding all valid subsets naively tests all $2^N$ integers.
The Rule: Initialize sub = mask. Repeatedly update sub = (sub - 1) & mask until sub == 0.
The Result: Visited states are guaranteed to be exact subsets of mask, running in $O(2^k)$ where $k$ is the number of set bits.

💡 The Ultimate Takeaway Decision Rule:
When analyzing an integer or parity problem, ask: "Is there pair cancellation, bit counting, or subset state packing?"

If Unpaired / Missing element ➔ XOR Accumulation ( $O(N)$ time, $O(1)$ space).

If Counting 1-bits or Power of 2 ➔ n & (n - 1) or n & (-n) surgery.

If Small state space ( $N \le 20$ ) ➔ Integer bitmask representation with 1 << i.

If 3-repeat occurrences ➔ Mod-3 state machine with ones and twos.

🎯 The 5 Essential Bit Manipulation Paradigms & Archetypes

Code / Blueprint

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                   THE 5 CORE BIT MANIPULATION ARCHETYPES                                         │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ Core Operation       │ Algebraic Invariant           │ Target Problems & Complexity     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. XOR Cancellation    │ `res ^= num`         │ `x ^ x = 0`, `x ^ 0 = x`      │ Single Number (LC 136), Missing  │
│    (Accumulation)      │ `lowbit = diff&-diff`│ Commutative & Associative     │ Number (LC 268) — O(N), O(1)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Lowest-Bit Surgery  │ `n &= (n - 1)`       │ `n & (n - 1)` clears low bit; │ Hamming Weight (LC 191), Power   │
│    (Popcount / Lowbit) │ `lowbit = n & -n`    │ `n & -n` isolates low bit     │ of Two (LC 231) — O(k), O(1)     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. Masks & Sub-Masks   │ `1 << i`,            │ `(n >> i) & 1` tests bit i;   │ Subsets (LC 78), Partition to K  │
│    (Subset Packing)    │ `(sub - 1) & mask`   │ `(sub - 1) & mask` steps sub  │ Equal Subsets (LC 698) — O(2^N)  │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Mod-K State Machine │ `ones = (ones^x)&~two│ Bit registers track counts    │ Single Number II (LC 137) —      │
│    (Residue Counters)  │ `twos = (twos^x)&~one│ modulo K in O(1) space        │ O(N) time, O(1) space            │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 5. Whole-Word Arith.   │ `(a & b) << 1`       │ Fixed mask & shift steps      │ Reverse Bits (LC 190), Sum of    │
│    (Bit Re-arrangement)│ `a ^ b` (half-adder) │ replaces multi-step loops     │ Two Integers (LC 371) — O(1)     │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘

⚡ 1. XOR Cancellation & Bucket Splitting (LC 136 & 260)

Mental Model: XOR cancels duplicate pairs. When two unique elements remain, total_xor = a ^ b. Isolate any differing bit with diff_bit = total_xor & -total_xor to partition all numbers into two disjoint buckets and solve each independently in $O(1)$ space!
Code: see the XOR Cancel card.

✂️ 2. Lowest-Set-Bit Surgery & Popcount (LC 191 & 231)

Mental Model: n & (n - 1) drops the lowest 1-bit; n & (-n) isolates it as a power of 2. A positive number n is a power of 2 if and only if n & (n - 1) == 0.
Code: see the Kernighan's Bit Trick card.

🎭 3. Masks & Sub-Mask Enumeration (LC 78 & 401)

Mental Model: An integer is a packed set of 32 booleans.
Code: see the Bitmask Subsets card.

🔄 4. Per-Bit Mod-K Finite State Machines (LC 137)

Mental Model: When elements appear 3 times and one appears once, XOR alone cannot cancel triples. Maintain two bit registers ones and twos where transitions reset to 0 upon the third occurrence.
Code: see the Per-Bit Counting card.

➕ 5. Whole-Word Arithmetic & Bit Re-arrangement (LC 190 & 371)

Mental Model: Full-adder simulation using a ^ b for sum without carry and (a & b) << 1 for carry propagation until carry becomes 0.
Code Blueprint:

Code / Blueprint

def getSum(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF
    while b:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK  # keep both inside 32 bits every round
    return a if a <= MAX_INT else ~(a ^ MASK)

🌳 Evaluating Bitwise Invariants & Low-Level State Machines

Understanding the behavior of two's complement and fixed bit widths is vital in interviews:

1. Two's Complement & Sign Extension

In two's complement arithmetic, -x = ~x + 1. This mathematical identity is why x & (-x) precisely isolates the lowest set bit.
In Python, integers have arbitrary precision and do not overflow to 32-bit negatives. To simulate 32-bit signed integers, mask with 0xFFFFFFFF and convert values exceeding 0x7FFFFFFF using ~(val ^ 0xFFFFFFFF).

2. Constant Time Complexity Invariants

Operating on 32-bit words takes strictly $O(1)$ time and $O(1)$ space.
Sub-mask iteration sub = (sub - 1) & mask takes total time $\sum_{k=0}^N \binom{N}{k} 2^k = 3^N$ , which is significantly faster than checking all pairs $4^N$ .

💡 Staff SWE Architectural Invariant:
Bitwise operations treat the integer word as a SIMD register of 32 or 64 independent parallel 1-bit execution units. When you can express logic with &, |, ^, and shifts, you eliminate branch mispredictions and achieve optimal single-cycle throughput.

Understanding Invariants: XOR Cancellation & Lowest-Bit Surgery

A bitwise operator is a whole-word instruction applying to all 32/64 bits in parallel in a single cycle. Algebraic cancellations turn quadratic scans into O(N) single passes with O(1) memory.

Lowest-Set-Bit Kernighan Invariant

Condition: While n > 0, execute n &= (n - 1)

Action: drops rightmost 1-bit in O(1) time without looping over all 32 bits

Subtracting 1 flips trailing zeros to 1s and the lowest 1 to 0; ANDing with n zeroes out the lowest set bit.

XOR Algebraic Cancellation Invariant

Condition: For any sequence where duplicates appear an even number of times

Action: accumulate stream with res ^= x

Because x ^ x = 0 and x ^ 0 = x, all paired entries annihilate to 0 regardless of order, leaving the lone odd element.

Common Questions

"In Single Number, why does XORing every element together leave just the one that appears once — doesn't the order the elements arrive in matter?"

It doesn't, and that's exactly the property that makes the one-line solution work: XOR is both its own inverse and commutative/associative, so pairs cancel regardless of where they sit in the array.

Every value that appears twice contributes x ^ x, which is 0 — the pair contributes nothing to the running result, no matter how far apart the two copies are or what's XORed in between them. Because XOR is commutative and associative, you can reorder the whole expression as if every pair were sitting right next to each other, even though they aren't in the actual array. What survives after every pair cancels is 0 ^ unique_value, which — by the other half of the identity, x ^ 0 = x — is just unique_value itself.

This is why a single for num in nums: res ^= num pass, in O(1) extra space, finds the unpaired element without ever building a frequency map: you're not counting occurrences at all, you're relying on pairs annihilating each other bit-by-bit, in parallel, across all 32/64 bits at once. It's also exactly why this trick needs adapting for harder variants: when duplicates appear three times instead of two (Single Number II), x ^ x ^ x = x survives instead of cancelling, so plain XOR is replaced by a mod-3 bit-counting state machine (ones/twos registers) instead. When there are two distinct unique values hiding among pairs (Single Number III), XORing everything together doesn't isolate either one — it gives their XOR — so the fix is different again: XOR everything first, take any set bit in that result (lowbit = xor & -xor) to find one position where the two uniques differ, and split the whole array into two groups by that bit; plain pairwise cancellation now finds one unique value per group.

Coach discussion points

1.
Why does n & (n - 1) clear the lowest set bit? Discuss the cascade of carries in n - 1.
2.
In Single Number II, how do ones and twos track modulo 3 logic without an array? What would a fourth register do?
3.
Contrast logical shift (>>>) vs arithmetic shift (>>) in Java/JS. Why does Python not have this issue, and how do you simulate 32-bit bounds in Python?
4.
Why is x ^ y a valid "difference detector" for Hamming distance? How does (x ^ y) turn into a count?
5.
When would plain XOR fail (e.g. "appears three times"), and why does splitting by lowbit = xor & -xor rescue Single Number III but not Single Number II?
6.
How does sub = (sub - 1) & mask visit every sub-mask exactly once? Prove it terminates and never revisits.
7.
When the constraint says n <= 20, which families become available, and what is the time/space cost of enumerating all 2^n masks?
8.
In Maximum XOR of Two Numbers, why must the mask grow strictly from MSB to LSB rather than any other order? What invariant breaks if you process bits LSB-first?
9.
Prove that max_xor never decreases across iterations, and that every bit it locks in was already proven achievable by two real numbers. Why does this guarantee optimality without ever comparing all $O(N^2)$ pairs?
10.
Contrast the hash-set prefix implementation with a classical bit-trie implementation of the same algorithm. What does the trie make explicit that the hash-set version hides, and when would the trie's O(N) (amortized) walk beat the hash-set's O(N) rebuild-per-bit?

Complexity analysis

Time Complexity:
- $O(1)$ for operations bounding to a fixed 32 or 64 bits (e.g. Reverse Bits).
- $O(k)$ where $k$ is the number of set bits (Brian Kernighan's).
- $O(N)$ for Single Number (iterating over the array).
Space Complexity: $O(1)$ auxiliary space for almost all pure bit manipulation problems.

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Iterating 32 times instead of using Brian Kernighan's algorithm: Checking all 32 bits with n >>= 1 always takes 32 iterations. Using n &= (n - 1) clears the lowest set bit in each step, executing in operations strictly proportional to the number of set bits.
Signed vs unsigned right shift: In Java, C++, and C#, using signed right shift >> on negative integers propagates the sign bit (1s), causing infinite loops. Always use unsigned right shift >>> or cast to unsigned.
Bitwise operator precedence: Bitwise operators (&, |, ^) have lower precedence than comparison operators (==, !=). Writing n & 1 == 1 evaluates 1 == 1 first, resulting in n & True.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES