[algorithms] Bit Manipulation 位元運算

視覺化概覽

flowchart TD
    A["位元運算\n以 A=1010, B=1100 為例"] --> B["AND &\n1010 & 1100\n= 1000\n兩者皆 1 才為 1"]
    A --> C["OR |\n1010 | 1100\n= 1110\n任一為 1 即為 1"]
    A --> D["XOR ^\n1010 ^ 1100\n= 0110\n不同為 1"]
    A --> E["NOT ~\n~1010\n= 0101\n全部翻轉"]
    A --> F["左移 <<\n1010 << 1\n= 10100\n等於 ×2"]
    A --> G["右移 >>\n1010 >> 1\n= 0101\n等於 ÷2"]

基本運算子

運算子	名稱	範例
&	AND	1010 & 1100 = 1000
|	OR	1010 | 1100 = 1110
^	XOR	1010 ^ 1100 = 0110
~	NOT	~1010 = 0101
<<	左移	0010 << 1 = 0100
>>	右移	0100 >> 1 = 0010

常用技巧

基本操作

// 獲取第 i 位
(n >> i) & 1
 
// 設定第 i 位為 1
n | (1 << i)
 
// 清除第 i 位
n & ~(1 << i)
 
// 翻轉第 i 位
n ^ (1 << i)

經典公式

// 消除最低位的 1
n & (n - 1)
 
// 獲取最低位的 1
n & (-n)
 
// 檢查是否為 2 的冪
n > 0 && (n & (n-1)) == 0
 
// 奇偶判斷
n & 1  // 1=奇, 0=偶

計算 1 的個數

int countOnes(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // 每次消除一個 1
        count++;
    }
    return count;
}

XOR 的神奇性質

a ^ a = 0      自己 XOR 自己 = 0
a ^ 0 = a      任何數 XOR 0 = 自己
a ^ b ^ b = a  XOR 兩次等於沒有

應用：找出只出現一次的數

// 其他數都出現兩次
int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;  // 成對的會消除
    }
    return result;
}

不用加法的加法

int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;  // 進位
        a = a ^ b;                  // 無進位和
        b = carry;
    }
    return a;
}

子集枚舉

枚舉所有子集

// n 個元素有 2^n 個子集
for (int mask = 0; mask < (1 << n); mask++) {
    // mask 的二進位表示選了哪些元素
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            // 第 i 個元素被選中
        }
    }
}

枚舉某集合的子集

// 枚舉 mask 的所有子集
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // sub 是 mask 的子集
}

狀態壓縮

用一個整數表示集合狀態：

{a, b, c} 對應 111 = 7
{a, c}    對應 101 = 5
{b}       對應 010 = 2
{}        對應 000 = 0

// 添加元素 i
state |= (1 << i)
 
// 移除元素 i
state &= ~(1 << i)
 
// 檢查元素 i
(state & (1 << i)) != 0
 
// 集合大小
Integer.bitCount(state)

常見應用

1. 狀態壓縮 DP
2. 集合操作
3. 權限系統
4. 圖的鄰接表示
5. 遊戲狀態

經典題目

1. 只出現一次的數字 - LeetCode 136
2. 只出現一次的數字 II - LeetCode 137
3. 只出現一次的數字 III - LeetCode 260
4. 2 的冪 - LeetCode 231
5. 位 1 的個數 - LeetCode 191
6. 漢明距離 - LeetCode 461
7. 子集 - LeetCode 78

快速參考表

操作	程式碼	說明
乘 2	n << 1	左移
除 2	n >> 1	右移
乘 2^k	n << k	-
取餘 2^k	n & ((1<<k)-1)	-
檢查偶數	(n & 1) == 0	-
取負數	~n + 1	補數
交換	a^=b; b^=a; a^=b	XOR 交換

相關檔案

• Java 實作：BitManipulation.java