Bitwise Basics基本運算

01為什麼需要它

看到這些關鍵字就想到它：旗標、開關、權限、遮罩、暫存器、打包成一個整數、只改某一位不動其他位、每一位代表一件事、乘除 2 的次方。

02核心概念

整數在記憶體裡是一排位元，第 i 位代表 2^i。把每一位當成一個獨立的開關，一個 32 位元整數就是 32 個布林值。五種基本運算都是逐位進行的：AND（&）兩邊都是 1 才是 1；OR（|）任一邊是 1 就是 1；XOR（^）兩邊不同才是 1；NOT（~）全部翻轉；移位 x << k 整排往左推 k 格、右邊補 0，等於乘以 2^k，x >> k 往右推、丟掉最低的 k 位，等於除以 2^k 向下取整。

為什麼取位、設位、清位不會誤傷其他位：這些運算的第 i 位結果只看兩個運算元的第 i 位，位與位之間互不影響。對任一位 b：b & 1 = b、b & 0 = 0、b | 0 = b、b | 1 = 1、b ^ 0 = b、b ^ 1 = 1 − b。所以拿一個遮罩 1 << i（只有第 i 位是 1）：x | mask 把第 i 位設成 1、其他位和 0 做 OR 保持原樣；x & ~mask 把第 i 位清成 0、其他位和 1 做 AND 保持原樣；x ^ mask 只翻轉第 i 位；(x >> i) & 1 把第 i 位移到最低位再取出。一次處理連續 w 位也一樣，(1 << w) − 1 是 w 個 1，左移到定位就是那一段的遮罩。

複雜度：固定寬度的整數上，每個運算都是一條 CPU 指令，時間 O(1)、空間 O(1)，沒有最好或最壞情況之分。空間省的是常數倍，但倍數不小：n 個布林值用 bool 陣列要 n 個位元組，打包成位元只要 ⌈n / 8⌉ 個位元組。最多 64 個元素的集合可以用一個 64 位元整數表示，交集是 a & b、並集是 a | b、差集是 a & ~b，一條指令就算完，雜湊集合則要逐個元素比對。Python 的整數沒有位寬上限，位數很多時運算成本和位數成正比，但在 64 位以內可以視為常數。

常見的坑有三個。優先序：C++ 的 == 比 & 優先，x & 1 == 0 其實是 x & (1 == 0)；兩種語言的 + 都比移位優先，1 << i - 1 是 1 << (i - 1)。一律加括號最保險。位寬與溢位：C++ 的 1 << 31 在 32 位元 int 上會跑進符號位變成負數，1 << 40 的移位量超過位寬，是未定義行為，64 位元要寫 1ull << k。負數與二補數：位元運算把負數當成二補數，−x = ~x + 1，所以 ~x = −x − 1；Python 裡 ~178 是 −179 而不是 77，要自己 & 0xFF，負數右移則是向下取整（-7 >> 1 是 −4）。這一篇是後面幾篇的零件：XOR 的抵消性質在 XOR Tricks，n & (n − 1) 清掉最低位的 1 在 Counting Bits，把整數當集合逐一列舉在 Subset Enumeration。

03演算法步驟

1. 1決定位元配置：第 0 位是最低位。每個布林值配一個位置，每段多位元欄位配起點 lo 與寬度 w，寫成具名常數，例如 READ = 1 << 2。
2. 2做遮罩：單一位是 1 << i；連續 w 位是 ((1 << w) − 1) << lo；多個旗標用 OR 組起來，例如 READ | WRITE。
3. 3查詢用 AND：(x >> i) & 1 得到 0 或 1；(x & mask) != 0 表示遮罩裡至少一位是 1，(x & mask) == mask 表示全部是 1；欄位用 (x >> lo) & ((1 << w) − 1)。
4. 4修改：設位 x |= mask、清位 x &= ~mask、翻轉 x ^= mask。寫入欄位先清再寫：x = (x & ~mask) | (v << lo)，v 必須小於 2^w，否則先截斷。
5. 5檢查位寬與型別：C++ 用無號型別，常數寫 1u 或 1ull，移位量要小於位寬；Python 需要固定位寬時自己 & ((1 << w) − 1)。和比較運算混用時一律加括號。

04互動示範

A = 178（10110010）、B = 108（01101100），點 A、B 的任一格就能翻轉那一位，下面的 AND、OR、XOR、NOT 與移位即時更新；輸入列藍色是 1，結果列綠色是 1、灰色是 0。預設的 A 最高位是 1，所以 A << 1 會把它擠出 8 位元外。最下面一區用黃色標出選中的第 i 位：預設第 3 位是 0，設位和翻轉結果相同、清位沒有變化；改選第 1 位（A 在這裡是 1），就能看到清位和翻轉把它變成 0。

05程式碼

取位、設位、清位、翻轉四個基本函式，加上讀寫一段多位元欄位。範例用和互動示範同一組 A、B，再用 Unix 權限 754、GPIO 暫存器與 RGB 色碼示範實際用法。Python 的整數沒有位寬，所以另外附上 32 位元截斷與二補數轉換；C++ 一律用無號型別，並把優先序與溢位兩個陷阱寫在程式碼裡。

# 位元編號：第 0 位是最低位（最右邊），第 i 位代表 2 的 i 次方
def get_bit(x, i):
    return (x >> i) & 1                  # 右移 i 位，再看最低位


def set_bit(x, i):
    return x | (1 << i)                  # OR：第 i 位強制變 1


def clear_bit(x, i):
    return x & ~(1 << i)                 # AND 上「只有第 i 位是 0」的遮罩


def toggle_bit(x, i):
    return x ^ (1 << i)                  # XOR：第 i 位 0 變 1、1 變 0


# 多位元欄位：從第 lo 位開始、寬 w 位
def get_field(x, lo, w):
    return (x >> lo) & ((1 << w) - 1)    # (1 << w) - 1 是 w 個 1


def set_field(x, lo, w, v):
    mask = ((1 << w) - 1) << lo
    return (x & ~mask) | ((v << lo) & mask)   # 先清掉那一段，再寫入


# Python 的整數沒有位寬，需要固定寬度時自己截斷
def to_u32(x):
    return x & 0xFFFFFFFF                # 只留低 32 位，當成無號數


def to_i32(x):
    x &= 0xFFFFFFFF
    return x - (1 << 32) if x >> 31 else x    # 第 31 位是 1 就是負數（二補數）


R, W, X = 4, 2, 1                        # Unix 權限：讀 100、寫 010、執行 001

if __name__ == "__main__":
    a, b = 0b10110010, 0b01101100        # 178、108，和互動示範同一組
    print(a & b, a | b, a ^ b)           # 32 254 222
    print(~a & 0xFF, ~a)                 # 77 -179（~a 等於 -a - 1，要自己套遮罩）
    print((a << 1) & 0xFF, a >> 1)       # 100 89
    print(get_bit(a, 3), get_bit(a, 4))  # 0 1
    print(set_bit(a, 3), clear_bit(a, 4), toggle_bit(a, 1))   # 186 162 176

    mode = 0o754                         # rwxr-xr--：擁有者 7、群組 5、其他人 4
    group = get_field(mode, 3, 3)
    print(group, (group & W) != 0)       # 5 False：群組不能寫
    mode = set_field(mode, 0, 3, R | W)  # 其他人改成 rw-
    print(oct(mode))                     # 0o756

    color = 0xFF8800                     # 0xRRGGBB
    print(get_field(color, 8, 8))        # 136（綠色通道 0x88）
    print(hex(set_field(color, 8, 8, 0x44)))   # 0xff4400

    print(-7 >> 1, to_u32(-1), to_i32(0xFFFFFFFE))   # -4 4294967295 -2

06練習題

• LeetCode 190Reverse Bits（逐位取出、逐位放入）Easy
• LeetCode 1009Complement of Base 10 Integer（NOT 要配遮罩，注意 0）Easy
• LeetCode 405Convert a Number to Hexadecimal（每次取低 4 位，負數用二補數）Easy
• LeetCode 1318Minimum Flips to Make a OR b Equal to c（逐位比較）Medium
• LeetCode 318Maximum Product of Word Lengths（26 位元整數當字母集合）Medium
• LeetCode 371Sum of Two Integers（不用加號做加法）Medium