> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Bit Manipulation

> Solve problems efficiently using bitwise operations

<img className="block rounded-lg" src="https://mintcdn.com/devweeekends/CHfRzoAmD5TGW2ch/images/dsa-techniques/22-bit-manipulation.svg?fit=max&auto=format&n=CHfRzoAmD5TGW2ch&q=85&s=9c857a262502678b9a49eb7721067db2" alt="Bit Manipulation Pattern" width="1080" height="1080" data-path="images/dsa-techniques/22-bit-manipulation.svg" />

## What is Bit Manipulation?

**Bit Manipulation** uses bitwise operators to solve problems at the binary level. It enables O(1) operations for many tasks and reduces space complexity.

Think of every integer as a row of light switches -- each switch is either ON (1) or OFF (0). Bit manipulation is the art of flipping, reading, and combining those switches directly, without converting to decimal. This is the language your CPU already speaks, which is why bitwise operations are as fast as operations can get.

Why does this matter for interviews? Bit manipulation lets you solve certain problems in O(1) space and O(n) time that would otherwise require hash sets or sorting. The XOR trick for "find the unique element" is a classic example: no extra memory, one pass, elegant. Interviewers love it because it tests whether you understand what is happening beneath the abstraction.

**Key mental model**: Every integer is a fixed-width binary string (32 or 64 bits in most languages). Operations like AND, OR, and XOR operate on each bit position independently and in parallel -- all 32 bits are processed in a single CPU instruction.

<Tip>
  **LeetCode Pattern Recognition Cheatsheet -- when to reach for bit manipulation:**

  * **"Find the single number"** -- every element appears twice except one (or thrice except one). XOR cancels pairs in O(1) space. (LC 136, 137, 260)
  * **"Count set bits / popcount"** -- bit hacks like Brian Kernighan run in O(popcount) instead of O(32). (LC 191, 338)
  * **"Power of two / power of four"** -- `n &amp; (n - 1) == 0` short-circuits the loop. (LC 231, 342)
  * **"Generate all subsets"** -- iterate `i` from 0 to `2^n - 1`. Each integer is a subset bitmask. (LC 78, 90)
  * **"Bitmask DP"** -- state space tracks which elements/cities/tasks are visited. Use when n is at most around 20-24. (LC 691, 1125, TSP)
  * **"Swap without temp / multiply or divide by 2"** -- shift operations are nearly free at the hardware level.
  * **"Find the missing number"** -- XOR with the full range cancels matched pairs. (LC 268)
  * **"Maximum XOR pair"** -- bit-trie greedy approach, scanning from MSB. (LC 421)
  * **"Hamming distance / total Hamming distance"** -- XOR plus popcount. (LC 461, 477)

  If the problem mentions a small set (n at most around 20), independent bit positions, parity, or "every element appears k times except one," XOR or bitmask is almost always the intended approach.
</Tip>

## Essential Operations

<CodeGroup>
  ```python Python theme={null}
  # Basic operators
  a & b   # AND: 1 only if both bits are 1
  a | b   # OR: 1 if either bit is 1
  a ^ b   # XOR: 1 if bits are different
  ~a      # NOT: flip all bits
  a << n  # Left shift: multiply by 2^n
  a >> n  # Right shift: divide by 2^n
  ```

  ```java Java theme={null}
  // Basic operators
  a & b   // AND: 1 only if both bits are 1
  a | b   // OR: 1 if either bit is 1
  a ^ b   // XOR: 1 if bits are different
  ~a      // NOT: flip all bits
  a << n  // Left shift: multiply by 2^n
  a >> n  // Right shift: divide by 2^n
  a >>> n // Unsigned right shift
  ```

  ```cpp C++ theme={null}
  // Basic operators
  a & b   // AND: 1 only if both bits are 1
  a | b   // OR: 1 if either bit is 1
  a ^ b   // XOR: 1 if bits are different
  ~a      // NOT: flip all bits
  a << n  // Left shift: multiply by 2^n
  a >> n  // Right shift: divide by 2^n
  ```
</CodeGroup>

## Common Tricks

Each trick exploits a specific property of binary representation. Understanding **why** each works is more important than memorizing the formulas.

<CodeGroup>
  ```python Python theme={null}
  # Check if nth bit is set (0-indexed from the right)
  # Shift n right so the target bit lands at position 0, then mask with 1
  (num >> n) & 1

  # Set nth bit to 1
  # Create a mask with only bit n set, then OR it in
  num | (1 << n)

  # Clear nth bit (set to 0)
  # Create a mask with every bit set EXCEPT bit n, then AND it
  num & ~(1 << n)

  # Toggle nth bit (flip 0->1 or 1->0)
  # XOR with a mask that has only bit n set
  num ^ (1 << n)

  # Check if power of 2
  # Powers of 2 have exactly one bit set: 8 = 1000, 8-1 = 0111, AND = 0000
  n > 0 and (n & (n - 1)) == 0

  # Get lowest set bit (isolate it)
  # -n is the two's complement: flips all bits and adds 1, so only the
  # lowest set bit survives the AND
  n & (-n)

  # Clear lowest set bit (turn it off)
  # n-1 flips the lowest set bit and all bits below it; AND removes it
  n & (n - 1)

  # Count set bits (Brian Kernighan's algorithm)
  # Each iteration removes exactly one set bit, so we loop popcount times
  count = 0
  while n:
      n &= n - 1    # Remove lowest set bit
      count += 1
  ```

  ```java Java theme={null}
  // Check if nth bit is set
  (num >> n) & 1

  // Set nth bit
  num | (1 << n)

  // Clear nth bit
  num & ~(1 << n)

  // Toggle nth bit
  num ^ (1 << n)

  // Check if power of 2
  n > 0 && (n & (n - 1)) == 0

  // Get lowest set bit
  n & (-n)

  // Clear lowest set bit
  n & (n - 1)

  // Count set bits
  Integer.bitCount(n)
  ```

  ```cpp C++ theme={null}
  // Check if nth bit is set
  (num >> n) & 1

  // Set nth bit
  num | (1 << n)

  // Clear nth bit
  num & ~(1 << n)

  // Toggle nth bit
  num ^ (1 << n)

  // Check if power of 2
  n > 0 && (n & (n - 1)) == 0

  // Get lowest set bit
  n & (-n)

  // Clear lowest set bit
  n & (n - 1)

  // Count set bits
  __builtin_popcount(n)
  ```
</CodeGroup>

## Pattern Variations

### 1. Single Number

The poster child of bit manipulation. XOR has three properties that make this work:

* **Self-inverse**: `a ^ a = 0` (any number XOR itself vanishes)
* **Identity**: `a ^ 0 = a` (XOR with zero changes nothing)
* **Commutative and associative**: order does not matter

So if you XOR every element, all pairs cancel out and only the unique element survives.

**Walked example**: nums = \[4, 1, 2, 1, 2] -- XOR all: 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4.

**Time: O(n). Space: O(1).** No hash set needed.

<CodeGroup>
  ```python Python theme={null}
  def single_number(nums):
      """Find element that appears once (others twice)"""
      result = 0
      for num in nums:
          result ^= num     # Pairs cancel: a ^ a = 0; unique value remains
      return result

  # XOR properties: a ^ a = 0, a ^ 0 = a, commutative + associative
  ```

  ```java Java theme={null}
  public int singleNumber(int[] nums) {
      // Find element that appears once (others twice)
      int result = 0;
      for (int num : nums) {
          result ^= num;
      }
      return result;
      // XOR properties: a ^ a = 0, a ^ 0 = a, commutative
  }
  ```

  ```cpp C++ theme={null}
  int singleNumber(vector<int>& nums) {
      // Find element that appears once (others twice)
      int result = 0;
      for (int num : nums) {
          result ^= num;
      }
      return result;
      // XOR properties: a ^ a = 0, a ^ 0 = a, commutative
  }
  ```
</CodeGroup>

### 2. Counting Bits

A beautiful DP-meets-bit-manipulation problem. The recurrence `result[i] = result[i >> 1] + (i & 1)` says: "the number of set bits in `i` equals the number of set bits in `i` with its last bit removed (`i >> 1`), plus whatever that last bit was (`i & 1`)."

**Walked example**: i=5 (binary 101). `i >> 1` = 2 (binary 10, has 1 set bit). `i & 1` = 1. So `result[5] = 1 + 1 = 2`. Correct: 101 has two 1-bits.

**Time: O(n). Space: O(n).**

<CodeGroup>
  ```python Python theme={null}
  def count_bits(n):
      """Count set bits for all numbers 0 to n"""
      result = [0] * (n + 1)
      for i in range(1, n + 1):
          # i >> 1 drops the last bit; i & 1 checks if the last bit is 1
          result[i] = result[i >> 1] + (i & 1)
      return result
  ```

  ```java Java theme={null}
  public int[] countBits(int n) {
      // Count set bits for all numbers 0 to n
      int[] result = new int[n + 1];
      for (int i = 1; i <= n; i++) {
          result[i] = result[i >> 1] + (i & 1);
      }
      return result;
  }
  ```

  ```cpp C++ theme={null}
  vector<int> countBits(int n) {
      // Count set bits for all numbers 0 to n
      vector<int> result(n + 1, 0);
      for (int i = 1; i <= n; i++) {
          result[i] = result[i >> 1] + (i & 1);
      }
      return result;
  }
  ```
</CodeGroup>

### 3. Subsets Using Bitmask

An elegant alternative to backtracking for generating subsets. Each integer from 0 to 2^n - 1 is a bitmask where bit `i` means "include `nums[i]`." The bitmask 5 (binary 101) represents the subset containing `nums[0]` and `nums[2]`.

This approach is often simpler to code and harder to get wrong than recursive backtracking, but it only works when n is small (n at most around 20, since 2^20 is about a million).

**Time: O(n \* 2^n). Space: O(1)** (excluding output).

<CodeGroup>
  ```python Python theme={null}
  def subsets(nums):
      """Generate all subsets using bitmask"""
      n = len(nums)
      result = []
      
      for mask in range(1 << n):     # Iterate over all 2^n bitmasks
          subset = []
          for i in range(n):
              if mask & (1 << i):    # If bit i is set, include nums[i]
                  subset.append(nums[i])
          result.append(subset)
      
      return result

  # Walkthrough with nums = [a, b, c]:
  #   mask=0 (000) -> []
  #   mask=1 (001) -> [a]
  #   mask=2 (010) -> [b]
  #   mask=3 (011) -> [a, b]
  #   mask=4 (100) -> [c]
  #   mask=5 (101) -> [a, c]
  #   mask=6 (110) -> [b, c]
  #   mask=7 (111) -> [a, b, c]
  ```

  ```java Java theme={null}
  public List<List<Integer>> subsets(int[] nums) {
      // Generate all subsets using bitmask
      int n = nums.length;
      List<List<Integer>> result = new ArrayList<>();
      
      for (int mask = 0; mask < (1 << n); mask++) {
          List<Integer> subset = new ArrayList<>();
          for (int i = 0; i < n; i++) {
              if ((mask & (1 << i)) != 0) {
                  subset.add(nums[i]);
              }
          }
          result.add(subset);
      }
      return result;
  }
  ```

  ```cpp C++ theme={null}
  vector<vector<int>> subsets(vector<int>& nums) {
      // Generate all subsets using bitmask
      int n = nums.size();
      vector<vector<int>> result;
      
      for (int mask = 0; mask < (1 << n); mask++) {
          vector<int> subset;
          for (int i = 0; i < n; i++) {
              if (mask & (1 << i)) {
                  subset.push_back(nums[i]);
              }
          }
          result.push_back(subset);
      }
      return result;
  }
  ```
</CodeGroup>

### 4. Missing Number

<CodeGroup>
  ```python Python theme={null}
  def missing_number(nums):
      """Find missing number in [0, n]"""
      n = len(nums)
      result = n  # Start with n (might be missing)
      
      for i, num in enumerate(nums):
          result ^= i ^ num
      
      return result
  ```

  ```java Java theme={null}
  public int missingNumber(int[] nums) {
      // Find missing number in [0, n]
      int n = nums.length;
      int result = n;  // Start with n (might be missing)
      
      for (int i = 0; i < n; i++) {
          result ^= i ^ nums[i];
      }
      return result;
  }
  ```

  ```cpp C++ theme={null}
  int missingNumber(vector<int>& nums) {
      // Find missing number in [0, n]
      int n = nums.size();
      int result = n;  // Start with n (might be missing)
      
      for (int i = 0; i < n; i++) {
          result ^= i ^ nums[i];
      }
      return result;
  }
  ```
</CodeGroup>

### 5. Reverse Bits

<CodeGroup>
  ```python Python theme={null}
  def reverse_bits(n):
      """Reverse bits of 32-bit unsigned integer"""
      result = 0
      for _ in range(32):
          result = (result << 1) | (n & 1)
          n >>= 1
      return result
  ```

  ```java Java theme={null}
  public int reverseBits(int n) {
      // Reverse bits of 32-bit unsigned integer
      int result = 0;
      for (int i = 0; i < 32; i++) {
          result = (result << 1) | (n & 1);
          n >>>= 1;  // Unsigned right shift
      }
      return result;
  }
  ```

  ```cpp C++ theme={null}
  uint32_t reverseBits(uint32_t n) {
      // Reverse bits of 32-bit unsigned integer
      uint32_t result = 0;
      for (int i = 0; i < 32; i++) {
          result = (result << 1) | (n & 1);
          n >>= 1;
      }
      return result;
  }
  ```
</CodeGroup>

## Classic Problems

<AccordionGroup>
  <Accordion title="1. Power of Two" icon="hashtag">
    **Check**: n greater than 0 and (n & (n-1)) equals 0

    **Why**: Power of 2 has exactly one bit set
  </Accordion>

  <Accordion title="2. Hamming Distance" icon="ruler">
    **Formula**: count set bits in (x ^ y)

    **Why**: XOR gives 1 where bits differ
  </Accordion>

  <Accordion title="3. Add Without Plus" icon="plus">
    **Pattern**: sum = a ^ b, carry = (a & b) left-shifted by 1

    **Why**: XOR adds without carry, AND gives carry positions
  </Accordion>

  <Accordion title="4. Maximum XOR" icon="bolt">
    **Pattern**: Build trie of binary representations

    **Why**: Greedily choose opposite bit for maximum XOR
  </Accordion>
</AccordionGroup>

## Bit Manipulation in DP

<CodeGroup>
  ```python Python theme={null}
  def can_partition(nums):
      """Subset sum using bitset DP"""
      bits = 1  # bits represents reachable sums
      
      for num in nums:
          bits |= bits << num
      
      total = sum(nums)
      return total % 2 == 0 and (bits >> (total // 2)) & 1
  ```

  ```java Java theme={null}
  public boolean canPartition(int[] nums) {
      // Subset sum using bitset DP
      int total = 0;
      for (int num : nums) total += num;
      if (total % 2 != 0) return false;
      
      int target = total / 2;
      boolean[] dp = new boolean[target + 1];
      dp[0] = true;
      
      for (int num : nums) {
          for (int j = target; j >= num; j--) {
              dp[j] = dp[j] || dp[j - num];
          }
      }
      return dp[target];
  }
  ```

  ```cpp C++ theme={null}
  bool canPartition(vector<int>& nums) {
      // Subset sum using bitset DP
      int total = accumulate(nums.begin(), nums.end(), 0);
      if (total % 2 != 0) return false;
      
      bitset<20001> bits;
      bits[0] = 1;
      
      for (int num : nums) {
          bits |= bits << num;
      }
      return bits[total / 2];
  }
  ```
</CodeGroup>

## Common Mistakes

<Warning>
  **Avoid These Pitfalls:**

  1. **Signed vs unsigned confusion**: Python integers have arbitrary precision, so `1 << 40` just works. But in Java/C++, `1 << 32` on an `int` is undefined behavior or wraps around. Use `1L << n` in Java for shifts beyond 31.
  2. **Operator precedence gotchas**: Bitwise operators have **lower** precedence than comparison operators in most languages. `x & 1 == 0` is parsed as `x & (1 == 0)` which is `x & 0`, not `(x & 1) == 0`. Always use parentheses: `(x & 1) == 0`.
  3. **Off-by-one in shifts**: `1 << n` creates a mask for bit n (0-indexed). Shifting by the bit-width (e.g., `1 << 32` for a 32-bit int) is undefined in C/C++ and produces 0 in Java. Know your language's rules.
  4. **Negative numbers and right shift**: In Java/C++, the arithmetic right shift (`>>`) sign-extends (fills with the sign bit). Use `>>>` in Java for unsigned right shift. In C++, right-shifting a negative number is implementation-defined.
  5. **Forgetting to handle n = 0 in power-of-two check**: `0 & (0 - 1) == 0` is true, but 0 is not a power of 2. Always include the `n > 0` guard.
</Warning>

## Quick Reference

| Operation    | Code                    | Description            |
| ------------ | ----------------------- | ---------------------- |
| Get bit      | `(n >> i) & 1`          | Get ith bit            |
| Set bit      | `n OR (1 left-shift i)` | Set ith bit to 1       |
| Clear bit    | `n & ~(1 left-shift i)` | Set ith bit to 0       |
| Toggle bit   | `n ^ (1 left-shift i)`  | Flip ith bit           |
| Lowest bit   | `n & (-n)`              | Isolate lowest set bit |
| Clear lowest | `n & (n-1)`             | Remove lowest set bit  |

## Operator and Trick Cheatsheet

A condensed reference you can re-derive in an interview. Memorize the *why*, not just the line.

| Goal                         | One-liner                          | Why it works                    |
| ---------------------------- | ---------------------------------- | ------------------------------- |
| AND                          | `a & b`                            | Both bits set                   |
| OR                           | `a \| b`                           | Either bit set                  |
| XOR                          | `a ^ b`                            | Bits differ                     |
| NOT                          | `~a`                               | Flip every bit (in fixed width) |
| Get bit i                    | `(n >> i) & 1`                     | Move bit i to position 0, mask  |
| Set bit i                    | `n \| (1 << i)`                    | Mask in a 1 at position i       |
| Clear bit i                  | `n & ~(1 << i)`                    | Mask out position i             |
| Toggle bit i                 | `n ^ (1 << i)`                     | XOR flips that bit              |
| Lowest set bit               | `n & (-n)`                         | Two's complement isolates it    |
| Clear lowest set bit         | `n & (n - 1)`                      | Brian Kernighan                 |
| Is power of 2?               | `n > 0 && (n & (n - 1)) == 0`      | Exactly one set bit             |
| Flip all bits in fixed width | `n ^ -1` (or `n ^ ((1 << w) - 1)`) | XOR with all-ones mask          |
| Multiply by 2                | `n << 1`                           | Left shift                      |
| Divide by 2 (unsigned)       | `n >> 1`                           | Logical right shift             |
| Swap without temp            | `a ^= b; b ^= a; a ^= b;`          | XOR cancels pairs               |

### Iterating Subsets of a Bitmask

A surgical trick that shows up in bitmask DP. Given a bitmask `mask`, enumerate every subset (including empty) in time proportional to the number of subsets, not the universe.

```python Python theme={null}
sub = mask
while True:
    process(sub)              # do work for this subset
    if sub == 0:
        break
    sub = (sub - 1) & mask    # next subset, walking downward
```

```java Java theme={null}
int sub = mask;
while (true) {
    process(sub);
    if (sub == 0) break;
    sub = (sub - 1) & mask;
}
```

```cpp C++ theme={null}
int sub = mask;
while (true) {
    process(sub);
    if (sub == 0) break;
    sub = (sub - 1) & mask;
}
```

**Why it works:** subtracting 1 from a non-zero bitmask flips the lowest set bit and turns on all bits below it. ANDing with `mask` strips the new lower bits that are not part of the original set. Each step lands on a strict subset of `mask`, eventually reaching 0. Total iterations: exactly `2^popcount(mask)`.

**Where it shows up:** sum-over-subsets DP, partition problems (LC 1125 Smallest Sufficient Team), travelling-salesman-style bitmask DP, "split set into two non-empty groups" interval problems.

## Worked LeetCode Problems

Six canonical bit problems mapped to the patterns above. Each one is a template you can copy-adapt in interviews.

### LC 136 -- Single Number (Easy)

**Pattern:** XOR cancellation. Every element appears twice except one.

```python Python theme={null}
def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x   # pairs cancel, the unique survives
    return result
```

XOR is associative and commutative, so we can mentally regroup the input as `(a ^ a) ^ (b ^ b) ^ ... ^ unique = unique`. O(n) time, O(1) space.

### LC 191 -- Number of 1 Bits (Easy)

**Pattern:** Brian Kernighan's algorithm.

```python Python theme={null}
def hammingWeight(n):
    count = 0
    while n:
        n &= n - 1     # clear the lowest set bit
        count += 1
    return count
```

Runs in O(popcount) iterations, not O(32). For sparse integers this is significantly faster than the naive `for i in range(32): count += (n >> i) & 1`.

### LC 338 -- Counting Bits (Easy, DP + bit insight)

**Pattern:** DP recurrence using the lowest-bit trick.

```python Python theme={null}
def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)   # i has popcount(i//2) plus parity bit
        # alternative: dp[i] = dp[i & (i - 1)] + 1
    return dp
```

Two valid recurrences:

* `dp[i] = dp[i >> 1] + (i & 1)` -- chop off the lowest bit, look up half.
* `dp[i] = dp[i & (i - 1)] + 1` -- clear the lowest set bit, add one.

Both are O(n) total. The second is more general and reusable.

### LC 268 -- Missing Number (Easy)

**Pattern:** XOR with the full range. Cancels every present number.

```python Python theme={null}
def missingNumber(nums):
    result = len(nums)              # XOR includes n
    for i, x in enumerate(nums):
        result ^= i ^ x             # cancels matched pair (i, x_i)
    return result
```

Works because `0 ^ 1 ^ ... ^ n` XOR'd against `nums` (which contains all but one of those values) leaves only the missing one. The `len(nums)` seed accounts for the upper bound `n` not being one of the loop indices.

### LC 78 -- Subsets (Medium, bitmask iteration)

**Pattern:** Each integer in `[0, 2^n)` is a subset bitmask.

```python Python theme={null}
def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = [nums[i] for i in range(n) if (mask >> i) & 1]
        result.append(subset)
    return result
```

For each mask, bit `i` decides whether `nums[i]` is included. Generates all `2^n` subsets in O(n \* 2^n) total -- same asymptotic cost as backtracking but with no recursion stack.

### LC 421 -- Maximum XOR of Two Numbers in an Array (Medium, trie + bit greedy)

**Pattern:** Build a binary trie of bits MSB-to-LSB. For each number, walk the trie greedily preferring the *opposite* bit to maximize XOR.

```python Python theme={null}
def findMaximumXOR(nums):
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)                   # add the next high bit to consider
        prefixes = {x & mask for x in nums}
        candidate = max_xor | (1 << i)     # hope this bit can be set in the answer
        # if any pair of prefixes XORs to candidate, that bit is achievable
        if any((candidate ^ p) in prefixes for p in prefixes):
            max_xor = candidate
    return max_xor
```

The trie approach is cleaner conceptually (build trie, query each number, O(32n) per pass) but the prefix-set approach above is O(32n) and fits in fewer lines. Either is acceptable in an interview.

<Warning>
  **Pitfalls and traps to know cold:**

  1. **Java `int` is 32-bit signed.** `1 << 31` is `Integer.MIN_VALUE`. For 64-bit shifts, use `1L << n`. Use `>>>` for logical (unsigned) right shift; `>>` sign-extends.
  2. **Negative numbers in two's complement.** `~n == -n - 1`. To flip all bits in a fixed width `w`, XOR with `(1 << w) - 1`, not with `~0` (which is `-1` in Java/C++ and arbitrary in Python).
  3. **Operator precedence is the silent killer.** `x & 1 == 0` is parsed as `x & (1 == 0)`. Always parenthesize: `(x & 1) == 0`.
  4. **Bitmask DP has a hard ceiling.** `2^n` states explode. Stay under roughly n equals 20-24 unless you can prune the state space.
  5. **Power-of-two check needs the zero guard.** `n & (n - 1) == 0` is also true for `n == 0`. Add `n > 0`.
  6. **Python integers are unbounded.** `~0` is `-1`, not a 32-bit complement. Mask with `& 0xFFFFFFFF` when you need fixed-width semantics (Reverse Bits, Add Without Plus).
  7. **Shift by the word width is undefined behavior in C/C++.** `1 << 32` on a 32-bit `int` is UB. In Java the shift amount is taken modulo 32 for `int` (so `1 << 32` is `1`, surprising the unwary).
</Warning>

<Tip>
  **The five lines you should be able to write under pressure:**

  * `n & (n - 1)` -- clear lowest set bit (popcount, power of 2)
  * `n & (-n)` -- isolate lowest set bit
  * `(mask >> i) & 1` -- read bit i
  * `mask | (1 << i)` -- set bit i
  * `sub = (sub - 1) & mask` -- next subset of `mask`
</Tip>

## Curated LeetCode List

A focused list grouped by sub-pattern. Solve in order; you will see the same five tricks reused.

| LC # | Problem                    | Difficulty | Sub-pattern               |
| ---- | -------------------------- | ---------- | ------------------------- |
| 136  | Single Number              | Easy       | XOR cancellation          |
| 191  | Number of 1 Bits           | Easy       | Brian Kernighan           |
| 231  | Power of Two               | Easy       | `n & (n - 1) == 0`        |
| 268  | Missing Number             | Easy       | XOR with range            |
| 338  | Counting Bits              | Easy       | DP plus bit recurrence    |
| 78   | Subsets                    | Medium     | Bitmask enumeration       |
| 137  | Single Number II           | Medium     | Bit-counting mod 3        |
| 260  | Single Number III          | Medium     | XOR plus partitioning bit |
| 371  | Sum of Two Integers        | Medium     | XOR plus carry loop       |
| 421  | Maximum XOR of Two Numbers | Medium     | Trie or prefix greedy     |
| 477  | Total Hamming Distance     | Medium     | Per-bit counting          |
| 1125 | Smallest Sufficient Team   | Hard       | Bitmask DP                |

## Practice Problems

| Problem          | Difficulty | Link                                                                                  |
| ---------------- | ---------- | ------------------------------------------------------------------------------------- |
| Single Number    | Easy       | [LeetCode 136](https://leetcode.com/problems/single-number/)                          |
| Number of 1 Bits | Easy       | [LeetCode 191](https://leetcode.com/problems/number-of-1-bits/)                       |
| Counting Bits    | Easy       | [LeetCode 338](https://leetcode.com/problems/counting-bits/)                          |
| Maximum XOR      | Medium     | [LeetCode 421](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) |

<Tip>
  **Interview Tip**: XOR is your best friend for "find the unique element" problems. Remember: a ^ a = 0 and a ^ 0 = a.
</Tip>

## Interview Questions

### 1. An array contains n numbers where every element appears twice except one. Find the unique element in O(n) time and O(1) space.

**What interviewers are really testing:** Whether XOR is your first instinct and whether you can explain the three properties (self-inverse, identity, associativity) that make it work. This is the gateway bit manipulation question.

**Strong Answer:**

* XOR all elements together. Every duplicate pair cancels out (`a ^ a = 0`), and the unique element survives (`a ^ 0 = a`). One pass, no extra memory.
* The three properties that make this work: self-inverse (`a ^ a = 0`), identity (`a ^ 0 = a`), and commutativity/associativity (order does not matter, so we can mentally regroup pairs).
* Walked example: `[4, 1, 2, 1, 2]` -- XOR all: `4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4`.
* Why not a hash set? A hash set works but uses O(n) space. The XOR approach is O(1) space, which is what makes it elegant. Interviewers specifically want to see that you reach for bitwise operations when the constraints demand zero extra space.

**Red flag answer:** "Use a hash map to count frequencies and find the one with count 1." That works but uses O(n) space and completely misses the bit manipulation insight the interviewer is testing.

**Follow-ups:**

1. What if every element appears three times except one? Does XOR still work? What technique handles this?
2. What if there are two unique elements (everything else appears twice)? How do you separate them using XOR?

***

### 2. How does `n & (n - 1)` work, and what problems does it solve?

**What interviewers are really testing:** Whether you understand the binary-level mechanics of this operation, not just the applications. This one expression solves power-of-two checks, Brian Kernighan's popcount, and more.

**Strong Answer:**

* `n - 1` flips the lowest set bit of `n` and sets all bits below it. So `n & (n - 1)` turns off the lowest set bit and leaves everything else unchanged. Example: `n = 12` (binary `1100`), `n - 1 = 11` (binary `1011`), `n & (n-1) = 8` (binary `1000`) -- the lowest set bit (position 2) got cleared.
* Power-of-two check: a power of 2 has exactly one bit set. `n & (n - 1)` clears that single bit, giving 0. So `n > 0 and (n & (n - 1)) == 0` is the O(1) power-of-two test. The `n > 0` guard is essential because `0 & (-1) == 0` is also true, but 0 is not a power of 2.
* Brian Kernighan's algorithm: to count set bits (popcount), repeatedly apply `n = n & (n - 1)` until `n` becomes 0, counting iterations. Each iteration removes exactly one set bit, so the loop runs exactly `popcount(n)` times -- much faster than checking all 32 bits when the number has few set bits.
* This trick also detects whether a number is a power of 4 (must be power of 2 AND have its single set bit in an even position: `n & 0x55555555 == n`).

**Red flag answer:** "I memorized that `n & (n-1)` checks for power of two." Without being able to explain the bit-level mechanics, the candidate cannot adapt the trick to novel problems.

**Follow-ups:**

1. How would you count the number of set bits in all integers from 0 to n using the DP recurrence `result[i] = result[i & (i-1)] + 1`?
2. What is the Hamming distance between two integers, and how does XOR combined with popcount compute it?

***

### 3. Generate all subsets of an array using bitmasks. When is this better than backtracking?

**What interviewers are really testing:** Whether you can map the concept of subset inclusion/exclusion to binary representation and understand the practical trade-offs versus recursive backtracking.

**Strong Answer:**

* Each integer from 0 to `2^n - 1` represents a subset. Bit `i` being set means "include `nums[i]`." Iterate through all `2^n` masks, and for each mask, iterate through n bits to build the subset. Total time: O(n \* 2^n).
* Example: for `nums = [a, b, c]`, mask `5` (binary `101`) represents `[a, c]`. Mask `0` is the empty set, mask `7` (`111`) is the full set.
* When it is better than backtracking: the bitmask approach is iterative, so there is no recursion overhead and no risk of stack overflow. It is also easier to reason about correctness -- you are guaranteed to enumerate exactly `2^n` subsets without duplicates. For n at most 20 (about a million subsets), it is practical and often simpler to code under interview pressure.
* When backtracking is better: for large n where you need to prune early (like "subsets with sum at most a target"), backtracking can skip entire branches. Bitmask enumeration always visits all `2^n` masks -- no pruning possible. Backtracking also generalizes to permutations and combinations, while bitmask is specific to subset enumeration.

**Red flag answer:** "Bitmask is always better because it avoids recursion." This ignores the inability to prune and the exponential memory for the bit range. Another red flag is not knowing the practical limit of n at most around 20 for bitmask enumeration.

**Follow-ups:**

1. How would you enumerate all subsets of size exactly k using bitmasks? What is the trick to go from one k-bit mask to the next lexicographic k-bit mask?
2. In competitive programming, people use bitmask DP (like Travelling Salesman). How does the bitmask represent the DP state?

***

### 4. Explain the difference between signed and unsigned right shift. Why does this matter in bit manipulation interviews?

**What interviewers are really testing:** Language-level understanding of how negative numbers interact with bitwise operations. This is a frequent source of bugs in Java and C++, and interviewers want to see awareness.

**Strong Answer:**

* Arithmetic right shift (`>>`) preserves the sign bit -- it fills new bits on the left with the sign bit (0 for positive, 1 for negative). Logical/unsigned right shift (`>>>` in Java) always fills with 0, regardless of the sign.
* In Java, this distinction is critical. `(-1) >> 1` is still `-1` (binary all-1s stays all-1s). `(-1) >>> 1` is `Integer.MAX_VALUE` (the sign bit becomes 0). If you are manipulating bits of a negative number and expecting zeros to appear, you must use `>>>`.
* In Python, integers have arbitrary precision, so there is no fixed bit width and `>>` always does arithmetic shift. Negative numbers in Python are conceptually infinite-width two's complement, which means `~0` is `-1` and bitwise operations on negatives need masking with `& 0xFFFFFFFF` to simulate 32-bit behavior.
* In C/C++, right-shifting a negative number is implementation-defined (the standard does not mandate arithmetic vs. logical). Most compilers do arithmetic shift, but relying on this is technically non-portable. Use unsigned types when doing bit manipulation to avoid surprises.

**Red flag answer:** "Right shift just divides by 2." This is true for positive numbers but wrong for negative numbers with logical shift. Another red flag is not knowing that Java has both `>>` and `>>>` or that C++ right-shift on negatives is implementation-defined.

**Follow-ups:**

1. What is two's complement and why do computers use it instead of sign-magnitude?
2. What does `Integer.MIN_VALUE >> 1` evaluate to in Java? What about `Integer.MIN_VALUE >>> 1`?

***

### 5. Find the missing number in an array containing n distinct numbers from the range \[0, n]. Solve it using bit manipulation.

**What interviewers are really testing:** Whether you can apply the XOR cancellation trick to a slightly different setup. The missing number problem has multiple solutions (math, XOR, sorting), and the XOR approach shows bit manipulation fluency.

**Strong Answer:**

* XOR all numbers from 0 to n, then XOR all elements in the array. Every number that appears in both cancels out, leaving only the missing number.
* Implementation: initialize `result = n`, then for each index `i`, XOR both `i` and `nums[i]` into result. After the loop, result is the missing number.
* Why this works: the indices `0, 1, ..., n-1` combined with the initial `n` give us exactly the complete range `[0, n]`. XOR-ing these with the array elements cancels all present numbers, leaving only the absent one.
* Alternative approach: use the sum formula `n*(n+1)/2 - sum(nums)`. This is simpler but can overflow for large n in languages with fixed-width integers. The XOR approach never overflows because XOR does not increase magnitude.

**Red flag answer:** "Sort the array and look for the gap." That is O(n log n) and misses the O(n) solutions entirely. The math approach is acceptable, but not mentioning XOR when the question explicitly says "bit manipulation" is a miss.

**Follow-ups:**

1. What if there are two missing numbers from the range \[0, n+1]? Can you still use XOR?
2. The sum formula `n*(n+1)/2` can overflow in 32-bit integers. At what value of n does this happen?

***

### 6. How do you add two integers without using the + or - operator? Walk through the bit-level logic.

**What interviewers are really testing:** Deep understanding of how binary addition works at the hardware level. This problem maps directly to how a CPU's adder circuit operates.

**Strong Answer:**

* Binary addition without a carry is just XOR: `1 + 1 = 0` (with carry), `1 + 0 = 1`, `0 + 0 = 0`. The carry for each bit position is AND: a carry is generated when both bits are 1.
* The algorithm: `sum = a ^ b` (add without carry), `carry = (a & b) << 1` (carry bits, shifted left because a carry at position k affects position k+1). Now add `sum` and `carry` -- but we cannot use `+`, so we repeat the process with `a = sum, b = carry` until there is no carry (`b == 0`).
* In Python, negative numbers require special handling because Python integers have unlimited width. You need to mask with `0xFFFFFFFF` to simulate 32-bit arithmetic and convert back from unsigned to signed at the end.
* This is literally how a ripple-carry adder works in hardware. XOR gates compute the sum bits, AND gates compute the carry bits, and the carry propagates through the chain. A carry-lookahead adder optimizes this by computing all carries in parallel.

**Red flag answer:** "Use `a - (-b)` to avoid the plus sign." This technically uses subtraction, which is not the spirit of the question. The interviewer wants the XOR/AND loop.

**Follow-ups:**

1. How do you handle subtraction without the minus operator?
2. What is the maximum number of iterations the loop can take for 32-bit integers? Why?

***

### 7. What are common bit manipulation pitfalls in interviews, and how do you avoid them?

**What interviewers are really testing:** Practical awareness and defensive coding habits. This is a meta-question that reveals whether the candidate has been burned by these issues before.

**Strong Answer:**

* Operator precedence: bitwise operators have lower precedence than comparison operators in Java, C++, and Python. `x & 1 == 0` is parsed as `x & (1 == 0)` = `x & 0`, not `(x & 1) == 0`. Always parenthesize: `(x & 1) == 0`. This bug is almost invisible during interviews.
* Integer overflow on shift: `1 << 31` in Java is `Integer.MIN_VALUE` (negative) because Java uses signed 32-bit ints. For 64-bit shifts, use `1L << n`. In C++, `1 << 32` on a 32-bit int is undefined behavior.
* The `n = 0` edge case: `0 & (0 - 1)` equals 0, which passes the power-of-two check, but 0 is not a power of 2. Always guard with `n > 0`.
* Python's unlimited precision: unlike Java/C++, Python integers grow arbitrarily. `~0` is `-1` (not a 32-bit complement). To simulate 32-bit behavior, mask with `& 0xFFFFFFFF`. This matters for reverse-bits and add-without-plus problems.
* Signed vs. unsigned confusion: In Java, there is no unsigned int type. Use `>>>` for unsigned right shift and `Integer.toUnsignedLong()` when needed. In C++, mixing signed and unsigned in comparisons triggers compiler warnings for good reason -- the implicit conversion can produce surprising results.

**Red flag answer:** "I have not encountered any issues with bit manipulation." This means the candidate has not done enough practice. Everyone who has seriously worked with bits has been bitten by precedence or shift-width bugs.

**Follow-ups:**

1. Write a function to reverse the bits of a 32-bit integer. What is the common off-by-one error people make?
2. How does the `bitset` data structure in C++ (or `BitSet` in Java) differ from manual bit manipulation? When would you use one over the other?

## Interview Deep-Dive

<AccordionGroup>
  <Accordion title="When would you choose bit manipulation over a HashMap or sorting-based approach? What are the precise conditions where bit tricks provide an advantage?">
    **Strong Answer:**

    * Bit manipulation wins when the problem involves **finding unique elements among duplicates** and you need O(1) space. The XOR trick for "find the single number" uses zero extra memory -- a HashMap uses O(n) space for the same result.
    * **Condition 1 -- Duplicate cancellation.** When elements appear in pairs (or triples with bit-counting), XOR or bitwise counting can cancel them without storing anything. This is impossible with sorting (O(n log n) time) or hashing (O(n) space).
    * **Condition 2 -- Set representation.** When you need to track subsets of a small universe (n less than 32 or 64), bitmasks replace HashSets. Each subset is a single integer, set operations become bitwise OR/AND/XOR, and iteration over subsets uses `n & (n-1)` tricks. Bitmask DP for TSP (Travelling Salesman) uses this: state is a bitmask of visited cities, which would be an exponentially large set otherwise.
    * **Condition 3 -- Arithmetic properties.** Problems involving powers of 2, parity, or binary representations are naturally bit-manipulation problems. Checking power of 2 is `n & (n-1) == 0` -- O(1) versus converting to binary string and counting.
    * **When NOT to use bit manipulation:** When the problem has no inherent binary structure, bit tricks become obfuscation rather than optimization. If a HashMap solution is clear and within time/space constraints, prefer readability.
    * **Practical limit:** Bitmask approaches work for sets of size up to \~20-25 (since 2^25 = 33 million states). Beyond that, the exponential state space makes bitmask DP infeasible.

    **Follow-up: In the "Single Number II" problem where every element appears three times except one, XOR alone does not work. What technique do you use instead, and what is the complexity?**

    * You need **bitwise counting modulo 3.** For each bit position (0 through 31), count how many numbers have that bit set. If the count modulo 3 is 1, the unique number has that bit set; if 0, it does not.
    * Implementation: use two variables `ones` and `twos` that track bits appearing once and twice respectively. The state machine transitions: `ones = (ones ^ num) & ~twos`, `twos = (twos ^ num) & ~ones`. After processing all numbers, `ones` holds the unique number.
    * Time: O(n). Space: O(1). The modular counting generalizes: for "every element appears k times except one," count each bit position modulo k.
  </Accordion>

  <Accordion title="Explain the bitmask subset enumeration technique. Given a bitmask representing a set, how do you iterate over all subsets of that set in O(2^popcount) time?">
    **Strong Answer:**

    * **The trick:** To enumerate all subsets of a bitmask `mask`, start from `mask` and repeatedly subtract 1 while masking with the original: `sub = (sub - 1) & mask`. This generates all subsets in decreasing order, terminating at 0.
    * **Why it works:** Subtracting 1 from a bitmask flips the lowest set bit and sets all lower bits. ANDing with `mask` ensures only bits from the original set survive. This systematically generates every combination of bits that are subsets of `mask`.
    * **Code:**

    ```
    sub = mask
    while sub > 0:
        # process subset 'sub'
        sub = (sub - 1) & mask
    # also process sub = 0 (empty set) if needed
    ```

    * **Complexity:** Exactly 2^popcount(mask) subsets are generated, each in O(1) time. If mask has k bits set, this is O(2^k) total. For k = 15, that is 32,768 subsets.
    * **Where this appears:** Bitmask DP problems where the transition requires iterating over all subsets of a state. For example, in the "Minimum Cost to Connect Clusters" problem, for each set S of nodes, you try all ways to partition S into two non-empty subsets S1 and S2 where S1 union S2 = S.
    * **Common mistake:** Forgetting to handle the empty subset (sub = 0). The loop `while sub > 0` excludes it. If you need the empty set, process it after the loop.

    **Follow-up: In bitmask DP for TSP, the state is dp\[mask]\[i] where mask is the set of visited cities and i is the current city. What is the time complexity, and why is this approach limited to roughly n = 20?**

    * There are 2^n possible masks and n possible current cities, giving 2^n \* n states. Each transition tries n-1 possible next cities. Total: O(n^2 \* 2^n).
    * For n = 20: 20^2 \* 2^20 = 400 \* 1,048,576 = \~419 million operations. Feasible in 1-2 seconds in C++, borderline in Python.
    * For n = 25: 25^2 \* 2^25 = 625 \* 33,554,432 = \~21 billion operations. Infeasible on any standard machine.
    * The exponential 2^n factor is inherent to TSP (NP-hard). Bitmask DP is the standard exact approach for small n.
  </Accordion>

  <Accordion title="You are given an array where every element appears twice except two elements that appear once. Find both unique elements using O(1) space.">
    **Strong Answer:**

    * XOR all elements. The result is `a ^ b` where a and b are the two unique elements. Since a != b, this XOR is non-zero -- at least one bit differs between a and b.
    * **Key step:** Find any set bit in `a ^ b`. The simplest way: `diff_bit = xor_all & (-xor_all)` (isolates the lowest set bit). This bit is set in one of a or b but not both.
    * **Partition the array** into two groups: elements with that bit set, and elements without. Each group contains exactly one unique element (because paired elements have the same bits and go to the same group). XOR each group independently to find a and b.
    * **Time: O(n). Space: O(1).** Two passes through the array (first to compute XOR, second to partition and XOR each group). Can be done in one pass with careful bookkeeping.
    * **Why this works:** The differentiating bit guarantees that a and b land in different groups. All paired elements land in the same group (both copies have the same bit value), so they cancel via XOR within their group.
    * **Edge case:** If the two unique elements differ in only the sign bit (one positive, one negative in two's complement), the algorithm still works because it operates on bit positions, not values.

    **Follow-up: Can you generalize this to finding three unique elements where everything else appears twice?**

    * XOR all elements gives `a ^ b ^ c`. You cannot directly extract individual values from a three-way XOR because you do not know which bits belong to which element.
    * One approach: find a bit where at least one pair of the three unique elements differs. Partition into two groups using that bit. One group has one unique element (solve with simple XOR), the other has two (solve with the two-unique-elements technique above).
    * This requires careful selection of the differentiating bit and is significantly more complex. In interviews, this is a staff-level follow-up -- most interviewers do not expect a complete solution but want to see your reasoning process.
  </Accordion>
</AccordionGroup>

## LeetCode Interview Q\&A

Four LeetCode-grinder-flavored questions you should be able to answer cold. Each one has a strong-answer framework, full code, senior follow-ups, common wrong answers, and further reading.

<AccordionGroup>
  <Accordion title="Q1: Single Number (LC 136) -- why does XOR work, and how would you generalize it?" icon="bolt">
    **Strong Answer Framework**

    1. State the three XOR axioms: `a ^ a = 0`, `a ^ 0 = a`, XOR is commutative and associative.
    2. Conclude: XORing the entire array regroups duplicates into pairs that cancel, leaving only the unique element.
    3. Note O(n) time, O(1) space.
    4. Mention the natural generalizations: LC 137 (every element appears 3 times) and LC 260 (two unique elements).

    **Real LeetCode Walkthrough -- LC 136**

    ```python Python theme={null}
    def singleNumber(nums):
        result = 0
        for x in nums:
            result ^= x
        return result
    ```

    Trace `[4, 1, 2, 1, 2]`: `0 ^ 4 = 4`, `4 ^ 1 = 5`, `5 ^ 2 = 7`, `7 ^ 1 = 6`, `6 ^ 2 = 4`. The unique element survives.

    <Note>
      **Senior follow-up 1: What if every element appears three times except one (LC 137)?**

      XOR alone fails because three copies of `a` XOR to `a`, not 0. Use bit-by-bit counting modulo 3, or the elegant two-variable state machine:

      ```python Python theme={null}
      def singleNumberII(nums):
          ones = twos = 0
          for x in nums:
              ones = (ones ^ x) & ~twos
              twos = (twos ^ x) & ~ones
          return ones
      ```

      `ones` tracks bits seen once mod 3, `twos` tracks bits seen twice mod 3. After three appearances both reset to 0.
    </Note>

    <Note>
      **Senior follow-up 2: What if there are two unique elements and everything else appears twice (LC 260)?**

      XOR all elements to get `a ^ b`. Pick any set bit (e.g., `diff = xor_all & -xor_all`). Partition the array by that bit -- `a` and `b` land in different groups, every duplicate pair lands in the same group. XOR each group to recover the two values.
    </Note>

    <Note>
      **Senior follow-up 3: What if the input is a stream and you cannot store all elements?**

      The XOR approach is *already* streaming -- you only keep `result`. That is what makes it elegant. Compare with hashing, which requires unbounded memory in the worst case.
    </Note>

    **Common Wrong Answers**

    * "Use a hash set" -- works but is O(n) space; misses the bit-manipulation insight the question is testing.
    * "Sort and find the lone element" -- O(n log n) time, mutates input, also misses the insight.
    * Using `ones` / `twos` for the simple LC 136 case -- over-engineered.

    **Further Reading**

    * LC 137 -- Single Number II
    * LC 260 -- Single Number III
    * LC 268 -- Missing Number (same XOR-with-range idea)
  </Accordion>

  <Accordion title="Q2: Counting Bits (LC 338) -- why is the DP recurrence dp[i] = dp[i & (i-1)] + 1 elegant?" icon="calculator">
    **Strong Answer Framework**

    1. Naive: for each `i` in `[0, n]`, run popcount via Brian Kernighan -- O(n log n) total.
    2. Better: notice `popcount(i) = popcount(i &amp; (i - 1)) + 1` because `i &amp; (i - 1)` is `i` with one set bit removed.
    3. Equivalent recurrence: `popcount(i) = popcount(i >> 1) + (i &amp; 1)`.
    4. Both are O(n) total because each `dp[i]` is one O(1) lookup plus an addition.

    **Real LeetCode Walkthrough -- LC 338**

    ```python Python theme={null}
    def countBits(n):
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i & (i - 1)] + 1
        return dp
    ```

    Trace small values:

    * `dp[1] = dp[0] + 1 = 1`
    * `dp[2] = dp[0] + 1 = 1`
    * `dp[3] = dp[2] + 1 = 2`
    * `dp[4] = dp[0] + 1 = 1`
    * `dp[5] = dp[4] + 1 = 2`

    Each `dp[i]` lookup walks one bit closer to zero -- the reason this is O(n) and not O(n log n).

    <Note>
      **Senior follow-up 1: Can you do it without DP, in O(n) time using a built-in?**

      Yes: `[bin(i).count('1') for i in range(n + 1)]` works in Python and runs in roughly O(n log n). Most languages have a hardware popcount instruction (`Integer.bitCount` in Java, `__builtin_popcount` in C++). The interviewer asking for the DP version is testing whether you can derive the recurrence; saying "use the builtin" misses the point.
    </Note>

    <Note>
      **Senior follow-up 2: What if n is enormous (say 10^9) but you only need the popcount of a few specific indices?**

      Skip the table entirely and run Brian Kernighan per query. Each query is O(popcount), at most 30 ops for 32-bit ints. Building a table of size 10^9 wastes memory you would not amortize.
    </Note>

    <Note>
      **Senior follow-up 3: How do you compute popcount of a 64-bit integer in O(1)?**

      Use the SWAR ("SIMD within a register") parallel-bit-count algorithm: a sequence of mask-and-add steps that combines pair counts, then nibble counts, then byte counts. Or just use `__builtin_popcountll` -- modern x86-64 has a single `POPCNT` instruction.
    </Note>

    **Common Wrong Answers**

    * Calling `bin(i).count('1')` inside the loop and claiming O(n) -- string conversion is O(log n).
    * Returning `dp[n]` instead of the entire array -- misreading the problem.
    * Off-by-one on the array size (allocating `n` instead of `n + 1`).

    **Further Reading**

    * LC 191 -- Number of 1 Bits (single integer popcount)
    * LC 461 -- Hamming Distance (XOR plus popcount)
    * LC 477 -- Total Hamming Distance (per-bit counting)
  </Accordion>

  <Accordion title="Q3: Iterate over all subsets of a set using a bitmask -- explain the trick and where it appears." icon="layer-group">
    **Strong Answer Framework**

    1. Represent the set as a bitmask `mask` of width n.
    2. To enumerate all `2^n` subsets: iterate `i` from 0 to `(1 << n) - 1`. Each `i` is a subset.
    3. To enumerate subsets of a *specific* mask (not the full universe): use `sub = (sub - 1) &amp; mask`, starting from `sub = mask`, until `sub` rolls over to 0.
    4. Total cost is exactly `2^popcount(mask)` iterations -- proportional to the number of subsets, not the universe.

    **Real LeetCode Walkthrough -- LC 78 Subsets**

    ```python Python theme={null}
    def subsets(nums):
        n = len(nums)
        result = []
        for mask in range(1 << n):
            subset = [nums[i] for i in range(n) if (mask >> i) & 1]
            result.append(subset)
        return result
    ```

    For `nums = [1, 2, 3]`, masks 0..7 each produce a distinct subset: `000` -> `[]`, `001` -> `[1]`, `010` -> `[2]`, `011` -> `[1,2]`, ..., `111` -> `[1,2,3]`.

    **Why subset-of-mask matters:** in bitmask DP (e.g., LC 1125 Smallest Sufficient Team, sum-over-subsets DP) you often need to iterate every subset of a given state. The naive double loop `for mask in range(1<<n): for sub in range(1<<n): if (sub &amp; mask) == sub` is O(4^n). The `(sub - 1) &amp; mask` trick is O(3^n) total across all masks (each ordered pair `(mask, sub)` with `sub` a subset of `mask` is visited exactly once).

    <Note>
      **Senior follow-up 1: Why is the total cost O(3^n) for sum-over-subsets DP?**

      For each of the `n` bits, three states are possible across the (mask, sub) pair: bit is in neither, bit is in mask only, bit is in both. That gives `3^n` total ordered pairs, which is exactly what the trick visits.
    </Note>

    <Note>
      **Senior follow-up 2: How would you generate subsets in lexicographic order instead of bitmask order?**

      Bitmask order is *not* lex order. For lex order use a Gray code or backtracking with explicit ordering. For LeetCode acceptance, bitmask order is fine -- the grader does not care about subset ordering.
    </Note>

    <Note>
      **Senior follow-up 3: What if n is too large for `2^n` (say n equals 40)?**

      Meet-in-the-middle: split the set in half, enumerate `2^{n/2}` subsets on each side, combine with hashing or sorting. Bumps the practical limit from around 20 to around 40. See LC 1755 Closest Subsequence Sum.
    </Note>

    **Common Wrong Answers**

    * Using backtracking and claiming it is O(2^n) better -- both are O(n \* 2^n); bitmask just removes recursion overhead.
    * Forgetting `mask = 0` (the empty subset) -- LC 78 expects it.
    * Confusing `(mask >> i) &amp; 1` (read bit i) with `(mask &amp; i)` (mask intersect i, very different).

    **Further Reading**

    * LC 78 / LC 90 -- Subsets, Subsets II
    * LC 1125 -- Smallest Sufficient Team (bitmask DP)
    * LC 691 -- Stickers to Spell Word (bitmask BFS)
  </Accordion>
</AccordionGroup>