位元運算教學：運算子、技巧與範例

位元運算解決什麼問題

整數是一排位元，許多問題其實就是在處理這些位元：像 rwx 的檔案權限、功能旗標、網路遮罩、像素顏色、精簡的選項集合、檢查碼與雜湊。位元運算子讓你一次運算就能讀取和修改許多位元，既節省記憶體，也非常快。

面試題也常用位元技巧，因為它們能得出優雅的 O(1) 空間解法，例如在其他數字都出現兩次時，找出唯一只出現一次的數字。

運算子

範例使用 a = 12（二進位 1100）和 b = 10（二進位 1010）。

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

單一位元的操作

位元位置從最右邊（最低有效位元）的 0 開始算。遮罩 1 << i 只有第 i 個位元為 1。

範例：計算設為 1 的位元數

Brian Kernighan 的方法會不斷清除最低位的 1，直到沒有為止，所以迴圈次數等於 1 的個數，而不是位元位置的個數。以 x = 44（二進位 101100）追蹤：

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() 從 Python 3.10 起可用。int.bit_length() 會回傳以二進位表示該數字所需的位元數（不含正負號）。

Python 中的經典技巧

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

遮罩 0 是空集合，5（二進位 101）是 ['a', 'c']，7 則是全部三個項目。位元遮罩動態規劃用的是同樣的概念，以遮罩作為狀態，適用於最多約 20 個項目的問題，例如小規模輸入的旅行推銷員問題。

另外兩個經典用法：x & 1 對奇數為 1；將 0 到 n 的所有數字與串列中的所有值一起做 XOR，就能找出唯一缺少的數字。

時間與空間複雜度

位元遮罩對每個可能的元素只用一個位元，所以 64 個旗標可以放進單一個 64 位元整數，而不是 64 個獨立的布林變數或串列元素。

常見錯誤

• 負數：Python 整數的行為就像有無限多個符號位元，所以 ~5 是 -6，而 bin(-5) 是 -0b101，不是二補數字串。若要看 32 位元的位元樣式，請先遮罩該值：-5 & 0xFFFFFFFF。
• Python 中負數的右移是算術右移：-8 >> 1 是 -4，而 -1 >> 10 仍是 -1。
• 固定位元寬度語言中的溢位：在 Java 或 C 中，32 位元 int 的 1 << 31 會變成負數或未定義行為；請使用 64 位元型別，並寫成 1L << 40 或 1ULL << 40。
• 混淆邏輯運算子與位元運算子：and 和 or（C 系語言中的 &&、||）回傳真假值，而 & 和 | 是逐位元運算。
• 可讀性：把 x * 2 換成 x << 1，在現代編譯器或 Python 中並不會更快，反而讓程式碼更難閱讀。

實際應用

• Unix 檔案權限：chmod 754 設定三組 3 位元的權限（rwx = 4 + 2 + 1）。
• 網路：IPv4 子網路遮罩，其中 ip & mask 可得出 CIDR 區塊的網路位址。
• 旗標與選項：Python 的 re.IGNORECASE | re.MULTILINE 與 enum.Flag 以 OR 組合選項。
• 圖形與顏色：24 位元 RGB 值以 (r << 16) | (g << 8) | b 打包紅、綠、藍。
• 資料結構與演算法：布隆過濾器、位元集、Fenwick 樹（使用 i & -i）、雜湊與檢查碼。
• 面試題目：只出現一次的數字、計算位元數、2 的冪、反轉位元、缺失的數字、用位元遮罩產生子集、不用 + 計算兩整數之和。