LeetCode Patterns - 22 Bit Manipulation

Post by ailswan June. 02, 2026

中文 ↓
LeetCode Patterns  · 

🎯 Bit Manipulation

1️⃣ Core Framework

When discussing Bit Manipulation, I frame it as:

  1. What bit manipulation solves
  2. Binary representation
  3. AND / OR / XOR
  4. Left shift / right shift
  5. Check, set, clear, toggle bit
  6. XOR patterns
  7. Bitmask patterns
  8. Subset generation
  9. Counting bits
  10. Senior-level explanation

2️⃣ What Problem Are We Solving?

Bit manipulation uses binary representation to solve problems efficiently.

It is commonly used for:

The core idea is:

Numbers are stored as bits.
Bit operations let us inspect, modify, combine, or compress state efficiently.

👉 Interview Answer

Bit manipulation is a technique that operates directly on the binary representation of numbers.

It is useful when the problem involves parity, uniqueness, subsets, flags, compressed states, or XOR relationships.

Common operations include AND, OR, XOR, NOT, and bit shifts.

3️⃣ Binary Representation

Decimal to Binary

Example:

5 = 101

Because:

5 = 4 + 1
  = 2^2 + 2^0

Bits

Each bit is either:

0 or 1

Example:

binary: 10110

From right to left:

bit 0 = 0
bit 1 = 1
bit 2 = 1
bit 3 = 0
bit 4 = 1

Important Idea

The rightmost bit is bit position 0.

1 << 0 = 1
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8

👉 Interview Answer

Binary representation stores a number as powers of two.

Each bit position represents whether a specific power of two is included.

Bit position 0 is the rightmost bit, and 1 << i represents the value of bit position i.

4️⃣ AND Operation

Operator

&

Rule

AND returns 1 only if both bits are 1.

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

Example

6 = 110
5 = 101

6 & 5 = 100 = 4

Common Use

AND is used to check whether a bit is set.

if num & (1 << i):
    print("bit i is set")

👉 Interview Answer

AND is used to test whether certain bits are present.

A common pattern is num & (1 << i).

If the result is non-zero, bit i is set.

If the result is zero, bit i is not set.

5️⃣ OR Operation

Operator

|

Rule

OR returns 1 if at least one bit is 1.

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

Example

6 = 110
5 = 101

6 | 5 = 111 = 7

Common Use

OR is used to set a bit.

num = num | (1 << i)

👉 Interview Answer

OR is commonly used to set bits.

If I want to turn bit i on, I can use num | (1 << i).

This keeps all existing bits and guarantees bit i becomes 1.

6️⃣ XOR Operation

Operator

^

Rule

XOR returns 1 if two bits are different.

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

Example

6 = 110
5 = 101

6 ^ 5 = 011 = 3

Important Properties

x ^ x = 0
x ^ 0 = x
x ^ y = y ^ x

👉 Interview Answer

XOR is useful because identical values cancel out.

Since x ^ x = 0 and x ^ 0 = x, XOR is commonly used to find a unique number when all other numbers appear twice.

7️⃣ NOT Operation

Operator

~

Meaning

NOT flips every bit.

0 becomes 1
1 becomes 0

Python Note

In Python:

~x == -x - 1

Example:

~5 == -6

This is because Python integers are not fixed-width.

Practical Use

When clearing bits, we often use:

num & ~(1 << i)

👉 Interview Answer

NOT flips bits.

In Python, ~x equals -x - 1 because Python integers are not fixed-width.

In interviews, NOT is often used together with AND to clear a specific bit.

8️⃣ Left Shift and Right Shift

Left Shift

x << k

Means:

multiply by 2^k

Example:

3 << 2 = 12

Because:

3 * 4 = 12

Right Shift

x >> k

Means:

divide by 2^k

For non-negative integers.

Example:

12 >> 2 = 3

Common Use

Create a mask:

1 << i

This creates a number with only bit i set.

👉 Interview Answer

Left shift moves bits to the left and is equivalent to multiplying by powers of two.

Right shift moves bits to the right and is equivalent to integer division by powers of two for non-negative integers.

The most common pattern is 1 << i, which creates a mask for bit i.

9️⃣ Check, Set, Clear, Toggle Bit

Check Bit

def is_set(num, i):
    return (num & (1 << i)) != 0

Set Bit

def set_bit(num, i):
    return num | (1 << i)

Clear Bit

def clear_bit(num, i):
    return num & ~(1 << i)

Toggle Bit

def toggle_bit(num, i):
    return num ^ (1 << i)

👉 Interview Answer

The basic bit operations are: use AND to check a bit, OR to set a bit, AND with NOT to clear a bit, and XOR to toggle a bit.

These operations are the foundation of most bit manipulation problems.

🔟 Single Number

Problem

Given an array where every number appears twice except one, find the single number.

XOR Idea

Since:

x ^ x = 0
x ^ 0 = x

All duplicate numbers cancel out.

Code

def single_number(nums):
    result = 0

    for num in nums:
        result ^= num

    return result

Example

nums = [4, 1, 2, 1, 2]

result = 4

👉 Interview Answer

For Single Number, I XOR all numbers together.

Every duplicate number cancels itself out, because x ^ x = 0.

The only number left is the one that appears once.

1️⃣1️⃣ Missing Number

Problem

Given numbers from 0 to n with one number missing, find the missing number.

XOR Idea

XOR all indices and all values.

The duplicate matched values cancel out.

The missing number remains.

Code

def missing_number(nums):
    result = len(nums)

    for i, num in enumerate(nums):
        result ^= i
        result ^= num

    return result

Alternative

def missing_number(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)

    return expected - actual

👉 Interview Answer

Missing Number can be solved with XOR.

I XOR all indices and all values.

Every number that appears in both places cancels out.

The remaining value is the missing number.

1️⃣2️⃣ Number of 1 Bits

Problem

Count how many 1 bits are in an integer.

Basic Approach

Check every bit:

def hamming_weight(n):
    count = 0

    while n:
        count += n & 1
        n >>= 1

    return count

Brian Kernighan’s Algorithm

Key trick:

n & (n - 1)

removes the lowest set bit.

Code

def hamming_weight(n):
    count = 0

    while n:
        n &= n - 1
        count += 1

    return count

👉 Interview Answer

To count set bits, I can repeatedly apply n & (n - 1).

This operation removes the lowest set bit from n.

Therefore, the number of times I can do this before n becomes zero is the number of 1 bits.

1️⃣3️⃣ Counting Bits

Problem

For every number from 0 to n, return the number of 1 bits.

DP Insight

For any number i:

bits[i] = bits[i >> 1] + (i & 1)

Because:

i >> 1 removes the last bit
i & 1 tells whether the last bit is 1

Code

def count_bits(n):
    result = [0] * (n + 1)

    for i in range(1, n + 1):
        result[i] = result[i >> 1] + (i & 1)

    return result

Alternative Insight

bits[i] = bits[i & (i - 1)] + 1

Because i & (i - 1) removes one set bit.

👉 Interview Answer

Counting Bits can be solved with DP.

For each number i, i >> 1 removes the last bit, and i & 1 tells whether the last bit was 1.

So bits[i] = bits[i >> 1] + (i & 1).

1️⃣4️⃣ Power of Two

Problem

Determine whether a number is a power of two.

Key Insight

A power of two has exactly one set bit.

Examples:

1  = 0001
2  = 0010
4  = 0100
8  = 1000

For power of two:

n & (n - 1) == 0

Code

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

👉 Interview Answer

A power of two has exactly one set bit.

The expression n & (n - 1) removes the lowest set bit.

Therefore, if n is positive and n & (n - 1) is zero, n is a power of two.

1️⃣5️⃣ Hamming Distance

Problem

Given two integers, return the number of bit positions where they differ.

XOR Idea

XOR marks different bits as 1.

Example:

x = 1  = 001
y = 4  = 100

x ^ y = 101

There are 2 set bits, so Hamming distance is 2.

Code

def hamming_distance(x, y):
    diff = x ^ y

    count = 0

    while diff:
        diff &= diff - 1
        count += 1

    return count

👉 Interview Answer

Hamming distance counts how many bit positions are different.

XOR gives 1 exactly where two bits differ.

So I XOR the two numbers, then count the number of set bits in the result.

1️⃣6️⃣ Reverse Bits

Problem

Reverse bits of a 32-bit unsigned integer.

Idea

Process 32 bits one by one.

For each bit:

shift result left
add current last bit of n
shift n right

Code

def reverse_bits(n):
    result = 0

    for _ in range(32):
        result <<= 1
        result |= n & 1
        n >>= 1

    return result

👉 Interview Answer

To reverse bits, I build the result from left to right.

Each iteration, I shift result left by one, take the lowest bit of n, append it to result, and then shift n right.

Since the input is 32-bit, I repeat this exactly 32 times.

1️⃣7️⃣ Bitmask for Subsets

Problem

Generate all subsets of an array.

Key Idea

For an array of length n, there are:

2^n

subsets.

Each subset can be represented by an n-bit mask.

Example

nums = [a, b, c]

Mask:

000 -> []
001 -> [a]
010 -> [b]
011 -> [a, b]
100 -> [c]
101 -> [a, c]
110 -> [b, c]
111 -> [a, b, c]

Code

def subsets(nums):
    n = len(nums)
    result = []

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])

        result.append(subset)

    return result

👉 Interview Answer

For subset generation, I can use a bitmask.

If the array has n elements, there are 2^n possible masks.

Each bit in the mask tells whether the corresponding element is included in the subset.

1️⃣8️⃣ Subsets With Duplicates

Problem

Generate all unique subsets when nums may contain duplicates.

Common Approach

Sorting + backtracking is usually simpler.

But bitmask can work with a set.

Code

def subsets_with_dup(nums):
    nums.sort()
    seen = set()
    result = []

    n = len(nums)

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])

        key = tuple(subset)

        if key not in seen:
            seen.add(key)
            result.append(subset)

    return result

Interview Note

For this problem, backtracking is usually preferred.

👉 Interview Answer

Bitmask can generate subsets with duplicates by using a set to remove duplicate subsets.

However, sorting plus backtracking is usually cleaner and more efficient for this specific problem.

Bitmask is best when elements are distinct or when we need compact state representation.

1️⃣9️⃣ Bitmask State Compression

What Is State Compression?

Instead of storing a set explicitly, we store it as an integer mask.

Example:

visited = {0, 2, 3}

Can be represented as:

mask = 1101

Because bits 0, 2, and 3 are set.

Common Operations

Add item:

mask |= 1 << i

Check item:

mask & (1 << i)

Remove item:

mask &= ~(1 << i)

Use Cases

visited states
subset DP
traveling salesman style problems
assignment problems
small-n combinatorics

👉 Interview Answer

Bitmask state compression represents a set as an integer.

Each bit indicates whether an item is included.

This is useful when n is small, usually up to around 20 to 25, because there are 2^n possible states.

2️⃣0️⃣ Bitmask DP

Problem Pattern

Bitmask DP is used when state depends on a subset of items.

Example:

dp[mask] = best answer for selected items represented by mask

Common Transition

Try adding one unused item:

for i in range(n):
    if not mask & (1 << i):
        next_mask = mask | (1 << i)

Code Skeleton

def bitmask_dp(n):
    dp = [float("inf")] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                continue

            next_mask = mask | (1 << i)
            dp[next_mask] = min(dp[next_mask], dp[mask] + cost(mask, i))

    return dp[(1 << n) - 1]

👉 Interview Answer

Bitmask DP is useful when the state is a subset of items.

I represent each subset as an integer mask.

Then I transition by adding or removing one item from the mask.

This is powerful for small-n combinatorial optimization problems.

2️⃣1️⃣ Find Two Single Numbers

Problem

Every number appears twice except two numbers. Find the two unique numbers.

XOR Idea

XOR all numbers:

xor = a ^ b

where a and b are the two unique numbers.

Since a != b, xor has at least one set bit.

Use that bit to separate numbers into two groups.

Code

def single_number_two(nums):
    xor = 0

    for num in nums:
        xor ^= num

    diff_bit = xor & -xor

    a = 0
    b = 0

    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num

    return [a, b]

Why xor & -xor?

It extracts the lowest set bit.

👉 Interview Answer

First, I XOR all numbers. Duplicates cancel out, leaving a ^ b, where a and b are the two unique numbers.

Since a and b are different, a ^ b has at least one set bit.

I use one set bit to split all numbers into two groups. Each group contains one unique number, and duplicates still cancel out inside each group.

2️⃣2️⃣ Single Number II

Problem

Every number appears three times except one number. Find the single number.

Bit Count Idea

For each bit position, count how many numbers have that bit set.

If every duplicate appears three times, then:

count % 3

reveals whether the unique number has that bit.

Code

def single_number(nums):
    result = 0

    for i in range(32):
        bit_count = 0

        for num in nums:
            bit_count += (num >> i) & 1

        if bit_count % 3:
            result |= 1 << i

    if result >= 2 ** 31:
        result -= 2 ** 32

    return result

Python Negative Number Note

Python integers are not fixed-width, so we manually convert 32-bit signed result if needed.

👉 Interview Answer

For Single Number II, XOR alone is not enough because duplicates appear three times.

I count set bits at each bit position.

Since duplicate numbers contribute multiples of three, bit_count % 3 tells whether the unique number has that bit set.

In Python, I also need to handle 32-bit signed negative numbers carefully.

2️⃣3️⃣ Maximum XOR of Two Numbers

Problem

Given an array, find the maximum XOR of two numbers.

High-Level Idea

XOR is maximized by making higher bits different.

A Trie of binary bits can help.

For each number, try to choose the opposite bit at each position.

Code Skeleton

class TrieNode:
    def __init__(self):
        self.children = {}


def find_maximum_xor(nums):
    root = TrieNode()

    for num in nums:
        node = root

        for i in range(31, -1, -1):
            bit = (num >> i) & 1

            if bit not in node.children:
                node.children[bit] = TrieNode()

            node = node.children[bit]

    answer = 0

    for num in nums:
        node = root
        current = 0

        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite = 1 - bit

            if opposite in node.children:
                current |= 1 << i
                node = node.children[opposite]
            else:
                node = node.children[bit]

        answer = max(answer, current)

    return answer

👉 Interview Answer

To maximize XOR, we want the highest bits to differ whenever possible.

I can insert all numbers into a binary Trie.

For each number, I greedily try to move to the opposite bit from the most significant bit to the least significant bit.

This builds the largest possible XOR value.

2️⃣4️⃣ Common Edge Cases

Zero

0 has no set bits

Some loops like:

while n:

will skip zero.

Negative Numbers

Python integers are not fixed-width.

For 32-bit problems, may need:

n & 0xffffffff

or signed conversion.

Overflow

In languages like Java or C++, integer overflow and signed shifts matter.

Large n in Bitmask

If n is too large:

2^n states become impossible

Bitmask subset generation usually only works for small n.

Boundary Bits

For 32-bit integers, loop over:

0 to 31

For signed integers, the highest bit is sign-related.

👉 Interview Answer

Common bit manipulation edge cases include zero, negative numbers, fixed-width integer behavior, overflow, and large bitmask state spaces.

In Python, negative numbers need special care because integers are not fixed-width.

2️⃣5️⃣ Common Mistakes

Mistake 1: Forgetting Parentheses

Wrong:

num & 1 << i

Better:

num & (1 << i)

Mistake 2: Confusing XOR and OR

OR sets bits.
XOR toggles bits.

Mistake 3: Using XOR When Counts Are Not Twice

XOR cancellation works naturally when duplicates appear exactly twice.

For three times, use bit counting.

Mistake 4: Ignoring Negative Numbers

Python negative numbers can break fixed-width assumptions.

Mistake 5: Bitmask With Too Many Elements

Subset bitmask is O(2^n).

Do not use it when n is large.

Mistake 6: Wrong Shift Direction

left shift increases magnitude
right shift removes lower bits

👉 Interview Answer

Common bit manipulation mistakes include forgetting parentheses around masks, confusing OR with XOR, using XOR cancellation when counts are not exactly twice, ignoring negative number behavior, using bitmask subsets for large n, and shifting in the wrong direction.

2️⃣6️⃣ When Bit Manipulation Applies

Good Fit

Use bit manipulation when the problem asks for:

unique number among duplicates
power of two
count set bits
parity
subset generation
state compression
flags
XOR relationship
Hamming distance
bit-level comparison

Problem Signals

Look for words like:

binary
bit
xor
power of two
unique
appears twice
appears three times
subset
mask
state
flag
toggle
Hamming

👉 Interview Answer

I consider bit manipulation when the problem involves binary representation, uniqueness with duplicates, XOR relationships, subset masks, state compression, or counting set bits.

Common signals include power of two, Hamming distance, appears twice, appears three times, and subset state.

2️⃣7️⃣ When Bit Manipulation Does Not Apply

Not Good Fit

Bit manipulation may not be ideal when:

state is not naturally binary
n is too large for subset masks
clarity matters more than micro-optimization
hashing or sorting is simpler
input involves arbitrary precision semantics

Better Alternatives

Problem Type Better Pattern
Count frequency generally HashMap
Sort and compare Sorting
Generate combinations with constraints Backtracking
Large subset optimization DP / Greedy / Graph
Range query on bits Prefix Count / Segment Tree
String prefix search Trie

👉 Interview Answer

Bit manipulation is powerful, but it is not always the clearest solution.

If a HashMap or sorting solution is simpler and meets the constraints, that may be better.

Bitmask techniques are mainly useful when the state space is small enough or the problem naturally maps to binary flags.

2️⃣8️⃣ Standard Templates

Check Bit

def is_set(num, i):
    return (num & (1 << i)) != 0

Set Bit

def set_bit(num, i):
    return num | (1 << i)

Clear Bit

def clear_bit(num, i):
    return num & ~(1 << i)

Toggle Bit

def toggle_bit(num, i):
    return num ^ (1 << i)

Remove Lowest Set Bit

n = n & (n - 1)

Get Lowest Set Bit

lowbit = n & -n

Count Set Bits

def count_ones(n):
    count = 0

    while n:
        n &= n - 1
        count += 1

    return count

Subset Bitmask Template

def subsets(nums):
    n = len(nums)
    result = []

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])

        result.append(subset)

    return result

Bitmask DP Template

def bitmask_dp(n):
    dp = [float("inf")] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                continue

            next_mask = mask | (1 << i)
            dp[next_mask] = min(dp[next_mask], dp[mask] + cost(mask, i))

    return dp[(1 << n) - 1]

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Bit manipulation operates directly on the binary representation of numbers.

Each integer can be viewed as a sequence of bits, where each bit represents whether a power of two is present.

The most common operations are AND, OR, XOR, NOT, left shift, and right shift.

AND is usually used to check whether a bit is set. OR is used to set a bit. AND with NOT is used to clear a bit. XOR is used to toggle a bit or cancel equal values.

One of the most important XOR properties is that x ^ x = 0 and x ^ 0 = x. This makes XOR useful for problems like Single Number, where every duplicate appears exactly twice.

Another important trick is n & (n - 1). This removes the lowest set bit from n. It is commonly used to count set bits and to check whether a number is a power of two.

Bitmasking is another major use case. If we have n items, a mask can represent a subset of those items. Bit i tells whether item i is included. This is useful for subset generation, visited-state compression, and bitmask DP.

Bitmask DP is useful when the state depends on a subset of items. A common pattern is dp[mask], where mask represents selected items. Transitions usually add or remove one bit from the mask.

For problems where every number appears three times except one, XOR alone is not enough. Instead, I count bits at each position and take the count modulo three.

In Python, negative numbers require special care because Python integers are not fixed-width. For 32-bit problems, I may need to mask with 0xffffffff or convert the final answer back into signed integer form.

At a senior level, I would explain: what each bit represents, which bit operation maps to the desired behavior, why XOR cancellation works, why n & (n - 1) removes the lowest set bit, when bitmask state compression is appropriate, and when a simpler HashMap, sorting, or DP solution is preferable.

⭐ Final Insight

Bit Manipulation 的核心不是“记几个 trick”。

它的核心是把数字或状态看成 binary flags。

Senior-level 的重点是：

每个 bit 代表什么， AND / OR / XOR 分别改变什么， XOR 为什么可以 cancel duplicate values， n & (n - 1) 为什么能移除 lowest set bit， bitmask 如何表示 subset 或 visited state， 什么时候 n 太大不能用 bitmask， 以及 Python negative numbers 为什么要小心。

能讲清楚这些， Bit Manipulation 就是一种处理 uniqueness、state compression、subset enumeration 和 binary logic 的核心技巧。

中文部分

🎯 Bit Manipulation

1️⃣ 核心框架

讨论 Bit Manipulation 时，我通常从：

  1. Bit manipulation 解决什么问题
  2. Binary representation
  3. AND / OR / XOR
  4. Left shift / right shift
  5. Check, set, clear, toggle bit
  6. XOR patterns
  7. Bitmask patterns
  8. Subset generation
  9. Counting bits
  10. 高级工程师解释方式

2️⃣ 要解决什么问题？

Bit manipulation 利用数字的 binary representation 来高效解决问题。

它常用于：

核心思想是：

数字本质上由 bits 组成。
Bit operations 可以高效检查、修改、组合或压缩状态。

👉 面试回答

Bit manipulation 是直接操作数字二进制表示的一种技巧。

当问题涉及 parity、uniqueness、subsets、flags、 compressed states 或 XOR relationships 时， bit manipulation 很有用。

常见操作包括 AND、OR、XOR、NOT 和 bit shifts。

3️⃣ Binary Representation

Decimal to Binary

Example:

5 = 101

因为：

5 = 4 + 1
  = 2^2 + 2^0

Bits

每个 bit 只能是：

0 or 1

Example:

binary: 10110

从右往左：

bit 0 = 0
bit 1 = 1
bit 2 = 1
bit 3 = 0
bit 4 = 1

Important Idea

最右边的 bit 是 bit position 0。

1 << 0 = 1
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8

👉 面试回答

Binary representation 会把一个数字表示成 powers of two。

每个 bit position 表示某个 power of two 是否被包含。

bit position 0 是最右边的 bit， 1 << i 表示第 i 位对应的 mask。

4️⃣ AND Operation

Operator

&

Rule

AND 只有在两个 bit 都是 1 时才返回 1。

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

Example

6 = 110
5 = 101

6 & 5 = 100 = 4

Common Use

AND 常用来检查某个 bit 是否 set。

if num & (1 << i):
    print("bit i is set")

👉 面试回答

AND 常用于测试某些 bits 是否存在。

常见写法是 num & (1 << i)。

如果结果不是 0， 说明 bit i 是 set 的。

如果结果是 0， 说明 bit i 没有 set。

5️⃣ OR Operation

Operator

|

Rule

OR 只要至少一个 bit 是 1， 结果就是 1。

1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0

Example

6 = 110
5 = 101

6 | 5 = 111 = 7

Common Use

OR 常用来 set 某个 bit。

num = num | (1 << i)

👉 面试回答

OR 通常用来 set bit。

如果我想把 bit i 打开， 可以使用 num | (1 << i)。

这个操作会保留原来的 bits， 同时保证 bit i 变成 1。

6️⃣ XOR Operation

Operator

^

Rule

XOR 在两个 bits 不同时返回 1。

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0

Example

6 = 110
5 = 101

6 ^ 5 = 011 = 3

Important Properties

x ^ x = 0
x ^ 0 = x
x ^ y = y ^ x

👉 面试回答

XOR 很有用， 因为相同值会互相 cancel。

因为 x ^ x = 0， 且 x ^ 0 = x， 所以 XOR 常用于 finding unique number， 尤其是其他 numbers 都出现两次的场景。

7️⃣ NOT Operation

Operator

~

Meaning

NOT 会翻转每个 bit。

0 变成 1
1 变成 0

Python Note

在 Python 中：

~x == -x - 1

Example:

~5 == -6

这是因为 Python integers 不是 fixed-width。

Practical Use

清除 bit 时， 常用：

num & ~(1 << i)

👉 面试回答

NOT 会 flip bits。

在 Python 中， ~x 等于 -x - 1， 因为 Python integers 不是固定宽度。

面试中， NOT 通常和 AND 一起使用， 用来 clear 某个 specific bit。

8️⃣ Left Shift and Right Shift

Left Shift

x << k

表示：

乘以 2^k

Example:

3 << 2 = 12

因为：

3 * 4 = 12

Right Shift

x >> k

表示：

除以 2^k

对于 non-negative integers。

Example:

12 >> 2 = 3

Common Use

创建 mask：

1 << i

这个数只有 bit i 是 set 的。

👉 面试回答

Left shift 会把 bits 向左移动， 对非负整数来说相当于乘以 powers of two。

Right shift 会把 bits 向右移动， 对非负整数来说相当于除以 powers of two。

最常见的 pattern 是 1 << i， 用来创建 bit i 的 mask。

9️⃣ Check, Set, Clear, Toggle Bit

Check Bit

def is_set(num, i):
    return (num & (1 << i)) != 0

Set Bit

def set_bit(num, i):
    return num | (1 << i)

Clear Bit

def clear_bit(num, i):
    return num & ~(1 << i)

Toggle Bit

def toggle_bit(num, i):
    return num ^ (1 << i)

👉 面试回答

基础 bit operations 包括： 用 AND 检查 bit， 用 OR 设置 bit， 用 AND + NOT 清除 bit， 用 XOR toggle bit。

这些操作是大多数 bit manipulation problems 的基础。

🔟 Single Number

Problem

给定一个 array， 除了一个 number 只出现一次， 其他 numbers 都出现两次， 找出这个 single number。

XOR Idea

因为：

x ^ x = 0
x ^ 0 = x

所有 duplicate numbers 会 cancel 掉。

Code

def single_number(nums):
    result = 0

    for num in nums:
        result ^= num

    return result

Example

nums = [4, 1, 2, 1, 2]

result = 4

👉 面试回答

Single Number 中， 我会把所有 numbers XOR 在一起。

每个 duplicate number 都会 cancel 自己， 因为 x ^ x = 0。

最后留下的就是只出现一次的 number。

1️⃣1️⃣ Missing Number

Problem

给定 0 到 n 的 numbers， 其中缺少一个 number， 找出 missing number。

XOR Idea

把所有 indices 和所有 values XOR 起来。

匹配的 values 会 cancel。

最后留下 missing number。

Code

def missing_number(nums):
    result = len(nums)

    for i, num in enumerate(nums):
        result ^= i
        result ^= num

    return result

Alternative

def missing_number(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)

    return expected - actual

👉 面试回答

Missing Number 可以用 XOR。

我把所有 indices 和所有 values 都 XOR 起来。

出现过的数字都会 cancel。

最后剩下的就是 missing number。

1️⃣2️⃣ Number of 1 Bits

Problem

统计一个 integer 中有多少个 1 bits。

Basic Approach

检查每一位：

def hamming_weight(n):
    count = 0

    while n:
        count += n & 1
        n >>= 1

    return count

Brian Kernighan’s Algorithm

关键技巧：

n & (n - 1)

会移除 lowest set bit。

Code

def hamming_weight(n):
    count = 0

    while n:
        n &= n - 1
        count += 1

    return count

👉 面试回答

统计 set bits 时， 可以反复使用 n & (n - 1)。

这个操作每次会移除 n 的 lowest set bit。

所以能执行多少次直到 n 变成 0， 就说明有多少个 1 bits。

1️⃣3️⃣ Counting Bits

Problem

对 0 到 n 的每个数字， 返回它们的 1 bits 数量。

DP Insight

对于任意数字 i：

bits[i] = bits[i >> 1] + (i & 1)

因为：

i >> 1 removes the last bit
i & 1 tells whether the last bit is 1

Code

def count_bits(n):
    result = [0] * (n + 1)

    for i in range(1, n + 1):
        result[i] = result[i >> 1] + (i & 1)

    return result

Alternative Insight

bits[i] = bits[i & (i - 1)] + 1

因为 i & (i - 1) 会移除一个 set bit。

👉 面试回答

Counting Bits 可以用 DP。

对每个数字 i， i >> 1 会移除最后一位， i & 1 表示最后一位是否是 1。

所以 bits[i] = bits[i >> 1] + (i & 1)。

1️⃣4️⃣ Power of Two

Problem

判断一个 number 是否是 power of two。

Key Insight

Power of two 只有一个 set bit。

Examples:

1  = 0001
2  = 0010
4  = 0100
8  = 1000

对于 power of two：

n & (n - 1) == 0

Code

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

👉 面试回答

Power of two 只有一个 set bit。

n & (n - 1) 会移除 lowest set bit。

所以如果 n 是正数， 并且 n & (n - 1) 等于 0， 那么 n 就是 power of two。

1️⃣5️⃣ Hamming Distance

Problem

给定两个 integers， 返回它们有多少个 bit positions 不同。

XOR Idea

XOR 会把不同的 bit 标记为 1。

Example:

x = 1  = 001
y = 4  = 100

x ^ y = 101

有 2 个 set bits， 所以 Hamming distance 是 2。

Code

def hamming_distance(x, y):
    diff = x ^ y

    count = 0

    while diff:
        diff &= diff - 1
        count += 1

    return count

👉 面试回答

Hamming distance 统计两个数字有多少个 bit positions 不同。

XOR 正好会在两个 bits 不同的位置产生 1。

所以先 XOR 两个 numbers， 再统计结果中的 set bits。

1️⃣6️⃣ Reverse Bits

Problem

Reverse 一个 32-bit unsigned integer 的 bits。

Idea

逐位处理 32 次。

每次：

result 左移一位
加入 n 当前最低位
n 右移一位

Code

def reverse_bits(n):
    result = 0

    for _ in range(32):
        result <<= 1
        result |= n & 1
        n >>= 1

    return result

👉 面试回答

Reverse bits 时， 我会从左到右构建 result。

每次把 result 左移一位， 取出 n 的最低位， 加入 result， 然后把 n 右移。

因为题目是 32-bit， 所以固定执行 32 次。

1️⃣7️⃣ Bitmask for Subsets

Problem

生成一个 array 的所有 subsets。

Key Idea

如果 array 长度是 n， 那么一共有：

2^n

个 subsets。

每个 subset 可以用一个 n-bit mask 表示。

Example

nums = [a, b, c]

Mask:

000 -> []
001 -> [a]
010 -> [b]
011 -> [a, b]
100 -> [c]
101 -> [a, c]
110 -> [b, c]
111 -> [a, b, c]

Code

def subsets(nums):
    n = len(nums)
    result = []

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])

        result.append(subset)

    return result

👉 面试回答

生成 subsets 时， 可以用 bitmask。

如果 array 有 n 个元素， 就有 2^n 个 masks。

mask 中每一位表示对应元素是否被加入当前 subset。

1️⃣8️⃣ Subsets With Duplicates

Problem

当 nums 中可能有 duplicates 时， 生成所有 unique subsets。

Common Approach

Sorting + backtracking 通常更简单。

但 bitmask 也可以配合 set 使用。

Code

def subsets_with_dup(nums):
    nums.sort()
    seen = set()
    result = []

    n = len(nums)

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])

        key = tuple(subset)

        if key not in seen:
            seen.add(key)
            result.append(subset)

    return result

Interview Note

这题通常更推荐 backtracking。

👉 面试回答

Bitmask 可以通过 set 去重来生成 subsets with duplicates。

但是这道题通常 sorting + backtracking 更清晰也更高效。

Bitmask 更适合 elements distinct， 或者需要 compact state representation 的问题。

1️⃣9️⃣ Bitmask State Compression

What Is State Compression?

不显式存一个 set， 而是把 set 压缩成一个 integer mask。

Example:

visited = {0, 2, 3}

可以表示成：

mask = 1101

因为 bits 0、2、3 是 set 的。

Common Operations

Add item:

mask |= 1 << i

Check item:

mask & (1 << i)

Remove item:

mask &= ~(1 << i)

Use Cases

visited states
subset DP
traveling salesman style problems
assignment problems
small-n combinatorics

👉 面试回答

Bitmask state compression 会把一个 set 表示成一个 integer。

每个 bit 表示某个 item 是否被包含。

当 n 比较小， 通常在 20 到 25 左右以内时， 这种方法非常有用， 因为总状态数是 2^n。

2️⃣0️⃣ Bitmask DP

Problem Pattern

Bitmask DP 用于 state 依赖某个 subset 的问题。

Example:

dp[mask] = mask 表示的 selected items 对应的 best answer

Common Transition

尝试加入一个 unused item：

for i in range(n):
    if not mask & (1 << i):
        next_mask = mask | (1 << i)

Code Skeleton

def bitmask_dp(n):
    dp = [float("inf")] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                continue

            next_mask = mask | (1 << i)
            dp[next_mask] = min(dp[next_mask], dp[mask] + cost(mask, i))

    return dp[(1 << n) - 1]

👉 面试回答

Bitmask DP 适合 state 是 items subset 的问题。

我用一个 integer mask 表示 subset。

然后通过添加或移除一个 item 来做状态转移。

它适合 small-n combinatorial optimization problems。

2️⃣1️⃣ Find Two Single Numbers

Problem

每个 number 都出现两次， 除了两个 numbers 只出现一次。 找出这两个 unique numbers。

XOR Idea

XOR 所有 numbers：

xor = a ^ b

其中 a 和 b 是两个 unique numbers。

因为 a != b， 所以 xor 至少有一个 set bit。

用这个 bit 把 numbers 分成两组。

Code

def single_number_two(nums):
    xor = 0

    for num in nums:
        xor ^= num

    diff_bit = xor & -xor

    a = 0
    b = 0

    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num

    return [a, b]

Why xor & -xor?

它可以取出 lowest set bit。

👉 面试回答

首先， 我把所有 numbers XOR 起来。 Duplicates 会 cancel， 最后得到 a ^ b， 其中 a 和 b 是两个 unique numbers。

因为 a 和 b 不同， 所以 a ^ b 至少有一个 set bit。

我用这个 set bit 把所有 numbers 分成两组。 每组里 duplicates 仍然会 cancel， 最后每组各剩一个 unique number。

2️⃣2️⃣ Single Number II

Problem

每个 number 出现三次， 只有一个 number 出现一次。 找出 single number。

Bit Count Idea

对每一个 bit position， 统计有多少 numbers 在这个 bit 上是 1。

如果 duplicates 都出现三次， 那么：

count % 3

就可以看出 unique number 在这个 bit 上是否是 1。

Code

def single_number(nums):
    result = 0

    for i in range(32):
        bit_count = 0

        for num in nums:
            bit_count += (num >> i) & 1

        if bit_count % 3:
            result |= 1 << i

    if result >= 2 ** 31:
        result -= 2 ** 32

    return result

Python Negative Number Note

Python integers 不是 fixed-width， 所以如果需要 32-bit signed result， 要手动转换。

👉 面试回答

Single Number II 中， XOR alone 不够， 因为 duplicates 出现三次。

我统计每个 bit position 上的 set bit 数量。

重复出现三次的 numbers 会贡献 3 的倍数。

所以 bit_count % 3 就能恢复 unique number 的 bit。

在 Python 中， 还需要小心处理 32-bit signed negative numbers。

2️⃣3️⃣ Maximum XOR of Two Numbers

Problem

给定一个 array， 找到两个 numbers 的最大 XOR。

High-Level Idea

XOR 最大化时， 我们希望高位尽量不同。

可以使用 binary Trie。

对每个 number， 从最高位到最低位， 尽量选择 opposite bit。

Code Skeleton

class TrieNode:
    def __init__(self):
        self.children = {}


def find_maximum_xor(nums):
    root = TrieNode()

    for num in nums:
        node = root

        for i in range(31, -1, -1):
            bit = (num >> i) & 1

            if bit not in node.children:
                node.children[bit] = TrieNode()

            node = node.children[bit]

    answer = 0

    for num in nums:
        node = root
        current = 0

        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            opposite = 1 - bit

            if opposite in node.children:
                current |= 1 << i
                node = node.children[opposite]
            else:
                node = node.children[bit]

        answer = max(answer, current)

    return answer

👉 面试回答

要最大化 XOR， 我们希望从最高位开始， 尽可能让两个 bits 不同。

我可以把所有 numbers 插入 binary Trie。

对每个 number， 从 most significant bit 到 least significant bit， greedy 地尝试走 opposite bit。

这样可以构造出最大的 XOR value。

2️⃣4️⃣ 常见 Edge Cases

Zero

0 has no set bits

类似：

while n:

这种 loop 会跳过 zero。

Negative Numbers

Python integers 不是 fixed-width。

对于 32-bit 问题， 可能需要：

n & 0xffffffff

或手动 signed conversion。

Overflow

在 Java 或 C++ 中， integer overflow 和 signed shifts 需要注意。

Large n in Bitmask

如果 n 太大：

2^n states become impossible

Bitmask subset generation 通常只适合 small n。

Boundary Bits

对于 32-bit integers， 通常 loop：

0 to 31

对于 signed integers， 最高位和 sign 有关。

👉 面试回答

Bit manipulation 常见 edge cases 包括 zero、 negative numbers、 fixed-width integer behavior、 overflow、 以及过大的 bitmask state space。

在 Python 中， negative numbers 特别需要小心， 因为 Python integers 不是 fixed-width。

2️⃣5️⃣ 常见错误

Mistake 1: 忘记 Parentheses

错误：

num & 1 << i

更清晰：

num & (1 << i)

Mistake 2: 混淆 XOR 和 OR

OR sets bits.
XOR toggles bits.

Mistake 3: Count 不是 Twice 时仍然用 XOR

XOR cancellation 最自然适用于 duplicates exactly twice。

如果出现三次， 通常用 bit counting。

Mistake 4: 忽略 Negative Numbers

Python negative numbers 会破坏 fixed-width assumptions。

Mistake 5: n 太大还用 Bitmask

Subset bitmask 是 O(2^n)。

n 大时不能用。

Mistake 6: Shift Direction 写反

left shift increases magnitude
right shift removes lower bits

👉 面试回答

Bit manipulation 常见错误包括： mask 忘记加 parentheses、 混淆 OR 和 XOR、 在 counts 不是 exactly twice 时错误使用 XOR cancellation、 忽略 negative number behavior、 对 large n 使用 subset bitmask， 以及 shift direction 写错。

2️⃣6️⃣ 什么时候 Bit Manipulation 适用？

Good Fit

当题目问：

unique number among duplicates
power of two
count set bits
parity
subset generation
state compression
flags
XOR relationship
Hamming distance
bit-level comparison

Problem Signals

看到这些关键词想到 Bit Manipulation：

binary
bit
xor
power of two
unique
appears twice
appears three times
subset
mask
state
flag
toggle
Hamming

👉 面试回答

当问题涉及 binary representation、 duplicates 中找 unique number、 XOR relationships、 subset masks、 state compression， 或 count set bits 时， 我会考虑 bit manipulation。

常见信号包括 power of two、Hamming distance、 appears twice、appears three times， 以及 subset state。

2️⃣7️⃣ 什么时候 Bit Manipulation 不适用？

Not Good Fit

Bit manipulation 不一定适合：

state is not naturally binary
n is too large for subset masks
clarity matters more than micro-optimization
hashing or sorting is simpler
input involves arbitrary precision semantics

Better Alternatives

Problem Type Better Pattern
Count frequency generally HashMap
Sort and compare Sorting
Generate combinations with constraints Backtracking
Large subset optimization DP / Greedy / Graph
Range query on bits Prefix Count / Segment Tree
String prefix search Trie

👉 面试回答

Bit manipulation 很强， 但不一定永远是最清晰的解法。

如果 HashMap 或 sorting solution 更简单， 并且满足 constraints， 那可能更好。

Bitmask 主要适合 state space 足够小， 或问题本身天然可以映射成 binary flags 的场景。

2️⃣8️⃣ 标准模板

Check Bit

def is_set(num, i):
    return (num & (1 << i)) != 0

Set Bit

def set_bit(num, i):
    return num | (1 << i)

Clear Bit

def clear_bit(num, i):
    return num & ~(1 << i)

Toggle Bit

def toggle_bit(num, i):
    return num ^ (1 << i)

Remove Lowest Set Bit

n = n & (n - 1)

Get Lowest Set Bit

lowbit = n & -n

Count Set Bits

def count_ones(n):
    count = 0

    while n:
        n &= n - 1
        count += 1

    return count

Subset Bitmask Template

def subsets(nums):
    n = len(nums)
    result = []

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])

        result.append(subset)

    return result

Bitmask DP Template

def bitmask_dp(n):
    dp = [float("inf")] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        for i in range(n):
            if mask & (1 << i):
                continue

            next_mask = mask | (1 << i)
            dp[next_mask] = min(dp[next_mask], dp[mask] + cost(mask, i))

    return dp[(1 << n) - 1]

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Bit manipulation 是直接操作数字 binary representation 的技术。

每个 integer 都可以看成一串 bits， 每个 bit 表示某个 power of two 是否存在。

最常见的 operations 是 AND、OR、XOR、NOT、left shift 和 right shift。

AND 通常用于检查某个 bit 是否 set。 OR 用于 set bit。 AND with NOT 用于 clear bit。 XOR 用于 toggle bit 或 cancel 相同值。

XOR 最重要的性质之一是 x ^ x = 0， 以及 x ^ 0 = x。 这让 XOR 非常适合 Single Number 这类问题， 其中其他 numbers 都恰好出现两次。

另一个重要技巧是 n & (n - 1)。 它会移除 n 的 lowest set bit。 这个技巧常用于 counting set bits， 以及判断一个 number 是否是 power of two。

Bitmasking 是另一个核心应用。 如果有 n 个 items， 一个 mask 可以表示这些 items 的一个 subset。 bit i 表示 item i 是否被选中。 这适合 subset generation、visited-state compression 和 bitmask DP。

Bitmask DP 适用于 state 取决于某个 subset 的问题。 常见写法是 dp[mask]， mask 表示 selected items。 状态转移通常通过添加或移除一个 bit 完成。

对于每个 number 出现三次， 只有一个 number 出现一次的问题， XOR alone 不够。 我会统计每个 bit position 的 count， 然后对 3 取模来恢复 unique number。

在 Python 中， negative numbers 要特别小心， 因为 Python integers 不是 fixed-width。 对 32-bit 问题， 可能需要使用 0xffffffff 做 mask， 或者把最终答案转换回 signed integer。

高级工程师解释 bit manipulation 时， 我会讲清楚： 每个 bit 代表什么， 哪个 bit operation 对应什么行为， 为什么 XOR cancellation 成立， 为什么 n & (n - 1) 可以移除 lowest set bit， 什么时候适合 bitmask state compression， 以及什么时候 HashMap、sorting 或 DP 会更简单。

⭐ Final Insight

Bit Manipulation 的核心不是“记几个 trick”。

它的核心是把数字或状态看成 binary flags。

Senior-level 的重点是：

每个 bit 代表什么， AND / OR / XOR 分别改变什么， XOR 为什么可以 cancel duplicate values， n & (n - 1) 为什么能移除 lowest set bit， bitmask 如何表示 subset 或 visited state， 什么时候 n 太大不能用 bitmask， 以及 Python negative numbers 为什么要小心。

能讲清楚这些， Bit Manipulation 就是一种处理 uniqueness、state compression、subset enumeration 和 binary logic 的核心技巧。

Implement