EP.21LeetCode 刷題日記

Bit Manipulation
位元操作的魔法

#191 Number of 1 Bits · #338 Counting Bits · #268 Missing Number · #136 Single Number — 用 XOR 與位移取代迴圈，寫出令人拍案的 O(1) 解法

Joseph Chen 2026 14 min read Bit Ops · XOR · Brian Kernighan

「你知道怎麼找出陣列裡唯一出現一次的那個數字嗎？」

面試官問這道題時，我第一直覺是用 HashMap。結果他說：「能不能不用額外空間？」 我卡住了。答案只需要一個 XOR 操作：把所有數字都 XOR 一遍， 相同的就抵消成 0，唯一剩下的就是答案。 這就是 Bit Manipulation 的魔法——用二進位的性質，把複雜問題變成一行。

位元操作基礎

在深入題目之前，把最常用的位元操作整理成一張速查表。 這六個操作是 Bit Manipulation 題目的全部武器庫。

操作符號範例常見用途
ANDa & b5 & 3 = 1 (101 & 011)取特定位、判斷奇偶 n & 1
ORa | b5 | 3 = 7 (101 | 011)設定特定位
XORa ^ b5 ^ 3 = 6 (101 ^ 011)找唯一值、swap、missing number
NOT~a~5 = -6 (反轉所有位)Python 少用，注意補數
左移a << k1 << 3 = 8 (× 2^k)快速計算 2 的冪次
右移a >> k8 >> 2 = 2 (÷ 2^k)取高位 / DP counting bits

XOR 三大性質（背起來！）

a ^ a = 0

相同值抵消

→ 找重複 / missing

a ^ 0 = a

與 0 XOR 不變

→ 初始值設 0

XOR 可交換結合

a^b^c = c^a^b

→ 順序不影響結果

#191

Number of 1 Bits

給一個整數，計算其二進位表示中有幾個 1（Hamming Weight）

Input: n = 11 (二進位 0b1011)

n = 11
0
0
0
0
1
0
1
1

三個位置有 1 → 回傳 3

方法一：逐位右移（直覺解）

每次用 n & 1 取最低位， 再 n >>= 1 右移，直到 n 為 0。

⏱ Time: O(32) = O(1)💾 Space: O(1)

方法二：Brian Kernighan 演算法（面試最愛）

關鍵觀察：n & (n-1) 會移除 n 的最低位的 1。 所以執行幾次操作、n 就變 0，次數就是 1 的個數。

n = 12（1100）的過程

1100& 1011= 1000移除最低 1（位置 2）
1000& 0111= 0000移除最低 1（位置 3）

count = 2 ✓（12 = 1100 只有 2 個 1）

⏱ Time: O(k)，k = 1 的個數💾 Space: O(1)
number_of_1_bits.py
def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)   # 移除最低位的 1
        count += 1
    return count

# 直覺版（逐位右移）
def hammingWeight_v2(n: int) -> int:
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Python 內建（面試不算分）
def hammingWeight_builtin(n: int) -> int:
    return bin(n).count('1')
#338

Counting Bits

給 n，回傳一個長度 n+1 的陣列，ans[i] = i 的二進位中 1 的個數

Input: n = 5

i012345
二進位011011100101
ans[i]011212

DP 解：右移 + 最低位

核心規律：把 i 右移一位（i >> 1）就是把最低位去掉， 所以 ans[i] = ans[i >> 1] + (i & 1)。

遞推驗證

i=210→ans[1] + 0=1（ans[1]=1, 最低位=0）
i=311→ans[1] + 1=2（ans[1]=1, 最低位=1）
i=4100→ans[2] + 0=1（ans[2]=1, 最低位=0）
i=5101→ans[2] + 1=2（ans[2]=1, 最低位=1）
⏱ Time: O(n)💾 Space: O(n)
counting_bits.py
def countBits(n: int) -> list[int]:
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

# 例：n=5 → [0, 1, 1, 2, 1, 2]

為什麼這個 DP 成立？

任何整數 i 的二進位，去掉最低位（i >> 1）就是 i/2 的二進位。 它的 1 的個數只比 i 多或少最低位那一個。 所以 ans[i] = ans[i/2] + (i是奇數?1:0)， 而且因為 i/2 一定比 i 小，前面的值已經計算好了，DP 成立。

#268

Missing Number

陣列包含 0 到 n 中的 n 個不同數字，找出缺少的那一個

Input: nums = [3, 0, 1]（n=3）

應該有 0,1,2,3 四個數，但只有三個 → 缺少的是 2

方法一：數學公式（簡單）

0～n 的總和 = n*(n+1)//2， 減去陣列實際的總和，差值就是缺少的數字。

⏱ Time: O(n)💾 Space: O(1)

方法二：XOR（面試加分）

把 「理想值 0,1,2,...,n」和「實際陣列值」全部 XOR 在一起。 出現兩次的數字互相抵消，只剩下缺少的那一個。

nums=[3,0,1] 的 XOR 過程

result = 0

i=0: result ^= 0 ^ nums[0] = 0 ^ 0 ^ 3 = 3

i=1: result ^= 1 ^ nums[1] = 3 ^ 1 ^ 0 = 2

i=2: result ^= 2 ^ nums[2] = 2 ^ 2 ^ 1 = 1

最後: result ^= n = 1 ^ 3 = 2 ✓

等效於：(0^1^2^3) ^ (3^0^1) = 2， 0,1,3 各出現兩次被抵消，只剩 2。

⏱ Time: O(n)💾 Space: O(1)
missing_number.py
def missingNumber(nums: list[int]) -> int:
    n = len(nums)

    # 方法一：數學公式（推薦）
    return n * (n + 1) // 2 - sum(nums)

def missingNumber_xor(nums: list[int]) -> int:
    n = len(nums)

    # 方法二：XOR
    result = n          # 先放入 n，讓 result = 0^1^...^n
    for i, num in enumerate(nums):
        result ^= i ^ num   # ^= i：加入理想值；^= num：抵消實際值
    return result
#136

Single Number

陣列中每個數字都出現兩次，只有一個數字出現一次，找出它

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

41212→ 回傳 4

XOR 一行解

利用 XOR 的交換結合律，把所有數字 XOR 在一起。 出現兩次的數字 a ^ a = 0， 只剩唯一出現一次的那個。

nums=[4,1,2,1,2] XOR 過程

4 ^ 1 ^ 2 ^ 1 ^ 2

= 4 ^ (1 ^ 1) ^ (2 ^ 2)   ← 重新排列

= 4 ^ 0 ^ 0

= 4 ✓

⏱ Time: O(n)💾 Space: O(1)
single_number.py
def singleNumber(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

# Python 一行版
def singleNumber_oneliner(nums: list[int]) -> int:
    from functools import reduce
    import operator
    return reduce(operator.xor, nums)

面試追問：如果有一個出現三次呢？（#137 Single Number II）

需要對每個 bit 位取模 3：用兩個變數 ones, twos， 分別記錄出現 1 次和 2 次的 bits，出現 3 次的 bit 就被清掉。 這是進階題，掌握基本 XOR 後再挑戰。

Bit Manipulation 解題模板

取最低位的 1

lowest_bit = n & (-n)
# 或: n & ~(n-1)

統計 1 的個數、找特定位

移除最低位的 1

n &= (n - 1)
# 每次移除最低的 1

#191 Number of 1 Bits

取第 k 位

bit_k = (n >> k) & 1
# k 從 0 開始

DP Counting Bits

XOR 找唯一值

result = 0
for num in nums:
    result ^= num

#136 Single Number、#268 Missing

各題解法比較

題目最優解法TimeSpace關鍵技巧
#191 Number of 1 BitsBrian KernighanO(k)O(1)n &= (n-1)
#338 Counting BitsDP + 右移O(n)O(n)ans[i] = ans[i>>1] + (i&1)
#268 Missing Number數學公式O(n)O(1)n*(n+1)/2 - sum
#136 Single NumberXOR AllO(n)O(1)a^a=0，成對抵消

本篇重點回顧

⚡Brian Kernighan：n &= (n-1) 每次移除最低位的 1，比逐位右移快
🔢Counting Bits DP：ans[i] = ans[i>>1] + (i&1)，右移一位就是去掉最低位
✨XOR 三性質：a^a=0、a^0=a、可交換結合 — 用來找唯一值或缺少的數
🎯Missing Number 兩解法：數學公式更直覺，XOR 是面試加分的進階解
💡Bit Manipulation 適用場景：只需 O(1) 空間、資料是整數、需要找「差異」或「唯一」

上一篇

EP.20 — Heap

Kth Largest、Top K Frequent、Find Median

下一篇

EP.22 — Math

Palindrome Number、快速冪、Happy Number、Count Primes

LeetCode
Bit Manipulation
XOR
Brian Kernighan
DP
Python
EP.21