[algorithms] Bit Manipulation 位元運算

位元運算是程式設計裡最接近硬體的操作。學會它不會讓你變成更好的工程師，但會讓你在面試和 code golf 裡看起來像個巫師。

先講結論

日常開發用到位元運算的機會不多，但面試愛考。權限系統、狀態壓縮 DP、效能優化——這幾個場景值得認識。核心就是 AND、OR、XOR 和位移，記住幾個公式就好。

六個基本運算子

運算子	名稱	範例（A=1010, B=1100）
&	AND	1010 & 1100 = 1000
|	OR	1010 | 1100 = 1110
^	XOR	1010 ^ 1100 = 0110
~	NOT	~1010 = 0101
<<	左移（×2）	0010 << 1 = 0100
>>	右移（÷2）	0100 >> 1 = 0010

必背的四個操作

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

必背的四個公式

n & (n - 1)         // 消除最低位的 1（經典中的經典）
n & (-n)            // 取得最低位的 1
n > 0 && (n & (n-1)) == 0  // 判斷 2 的冪
n & 1               // 判斷奇偶（1=奇, 0=偶）

n & (n - 1) 是什麼魔法？n-1 會把最低位的 1 變成 0，同時把它右邊的 0 全變成 1。AND 之後，最低位的 1 就消失了。

用這招數 1 的個數：

int countOnes(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

XOR 的三個性質

a ^ a = 0      自己 XOR 自己歸零
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;
}

成對的 XOR 歸零，剩下的就是答案。O(n) 時間 O(1) 空間。面試官問你能不能不用額外空間？這就是答案。

子集枚舉

n 個元素有 2^n 個子集。用 bitmask 表示「選了哪些」：

// {a,b,c} → 111=7, {a,c} → 101=5, {} → 000=0
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            // 第 i 個元素被選中
        }
    }
}

狀態壓縮

用一個整數表示集合狀態。在權限系統裡超常見：

int READ = 1;     // 001
int WRITE = 2;    // 010
int EXECUTE = 4;  // 100
 
int permission = READ | WRITE;  // 011 = 可讀可寫
boolean canRead = (permission & READ) != 0;  // true

Linux 的 chmod 755 就是這個原理。7 = 111 = rwx，5 = 101 = r-x。

狀態壓縮 DP 裡也是同樣的概念：用一個整數表示「哪些城市已經走過」，讓 DP 的狀態從集合變成數字。

快速參考

操作	寫法
乘 2	n << 1
除 2	n >> 1
取餘 2^k	n & ((1<<k)-1)
交換兩數	a^=b; b^=a; a^=b
取負數	~n + 1

---

位元運算就像魔術：看起來不可思議，但一旦知道原理就覺得理所當然。只是每次寫的時候還是要想一下。然後 debug 兩小時。