位操作基礎#
基本運算符#
| 運算符 | 名稱 | 規則 | 範例 |
|---|---|---|---|
& | AND | 兩位都為 1 才為 1 | 1010 & 1100 = 1000 |
| | OR | 有一位為 1 就為 1 | 1010 | 1100 = 1110 |
^ | XOR | 相異為 1，相同為 0 | 1010 ^ 1100 = 0110 |
~ | NOT | 0 變 1，1 變 0 | ~1010 = 0101 |
<< | 左移 | 左移 n 位 | 0011 << 2 = 1100 |
>> | 右移 | 右移 n 位 | 1100 >> 2 = 0011 |
XOR 的特殊性質#
XOR（異或）在演算法中極為常用：
| 性質 | 公式 | 說明 |
|---|---|---|
| 與 0 異或 | x ^ 0 = x | 保持原值 |
| 與全 1 異或 | x ^ 1s = ~x | 相當於取反 |
| 自我異或 | x ^ x = 0 | 結果為 0 |
| 交換律 | a ^ b = b ^ a | |
| 結合律 | (a ^ b) ^ c = a ^ (b ^ c) | |
| 可逆性 | A ^ B = C → C ^ B = A | 經典：不用臨時變數交換兩數 |
XOR 交換兩數
// 不使用臨時變數交換 a 和 b
a = a ^ b; // a = a^b
b = a ^ b; // b = a^b^b = a
a = a ^ b; // a = a^b^a = b三大核心技巧#
1. 判斷奇偶性：x & 1#
最後一位為 1 是奇數，為 0 是偶數。
if ((x & 1) == 1) {
// 奇數
} else {
// 偶數
}
x & 1比x % 2更高效（直接位操作 vs 除法運算）。
2. 清除最低位的 1：x & (x - 1)#
將 x 二進位中最右邊的 1 變為 0。
x = 1010...1000
x-1 = 1010...0111
x&(x-1) = 1010...0000應用：計算二進位中 1 的個數（Hamming Weight）
int count = 0;
while (x != 0) {
x = x & (x - 1);
count++;
}3. 取得最低位的 1：x & -x#
取出 x 二進位中最右邊的 1（Lowbit）。
x = ...10100
-x = ...01100 (補碼 = 取反 + 1)
x&-x = ...00100應用：樹狀陣列（Binary Indexed Tree）
進階操作#
更多位操作技巧
| 操作 | 公式 | 說明 |
|---|---|---|
| 取得第 n 位 | (x >> n) & 1 | 0 或 1 |
| 設置第 n 位為 1 | x | (1 << n) | |
| 清除第 n 位 | x & ~(1 << n) | |
| 切換第 n 位 | x ^ (1 << n) | 0→1, 1→0 |
| 保留最低 n 位 | x & ((1 << n) - 1) | |
| 判斷是否為 2 的冪 | x > 0 && (x & (x-1)) == 0 |
進行移位操作時，注意整數型態的位數限制和符號位處理，避免溢位或非預期結果。
位操作速記表#
十進位 二進位
6 = 110
11 = 1011
-1 = 1111...1111 (全1，補碼表示)在二補數表示法中，
-1的二進位表示是全 1（111...111），這是常見的面試考點。