位運算符速查表
| 運算符 | 名稱 | 規則 | 典型用途 |
|---|
& | 按位與 | 同1為1，其餘0 | 清零特定位、取指定位、判斷奇偶 |
| | 按位或 | 有1為1 | 置位特定位、合併標誌位 |
^ | 按位異或 | 異為1，同為0 | 翻轉特定位、無臨時變量交換、校驗和 |
~ | 按位取反 | 0↔1 | 構造掩碼、無符號數取反 |
<< | 左移 | 低位補0，高位丟棄 | 乘 2^n、構造掩碼 (1<<k) |
>> | 右移 | 有符號算術移位(符號位擴展)，無符號邏輯移位(高位補0) | 除 2^n、取高位 |
經典位操作模板（假設 int 32 位）
| 操作 | 代碼 | 說明 |
|---|
| 判斷奇偶 | (x & 1) == 0 偶數 / == 1 奇數 | 最低位決定 |
| 取第 k 位 (0-index) | (x >> k) & 1 | 右移 k 位後取最低位 |
| 清零第 k 位 | x &= ~(1 << k) | 掩碼該位為 0，其餘 1 |
| 置 1 第 k 位 | x |= (1 << k) | 掩碼該位為 1，其餘 0 |
| 翻轉第 k 位 | x ^= (1 << k) | 異或 1 翻轉，異或 0 不變 |
| 循環左移 k 位 | (x << k) | (x >> (32 - k)) | 高位繞到低位 |
| 循環右移 k 位 | (x >> k) | (x << (32 - k)) | 低位繞到高位 |
無分支編程技巧（Branchless Programming）
1. 平均值不溢出
int average(int x, int y) {
return (x & y) + ((x ^ y) >> 1);
}
// 原理：(x+y)/2 = (x&y) + (x^y)/2，避免 x+y 溢出
2. 判斷 2 的冪次
bool isPowerOfTwo(int x) {
return x > 0 && (x & (x - 1)) == 0;
}
// 原理：2^n 二進制只有 1 個 1，減 1 後該位變 0 低位全 1，與運算為 0
3. 無臨時變量交換
void swap(int* x, int* y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
// 注意：x==y 時會清零，實際用需加 if (x!=y) 判斷
4. 絕對值（無分支）
int abs(int x) {
int y = x >> 31; // 算術右移：正數全0，負數全1 (0xFFFFFFFF)
return (x ^ y) - y; // 正數: x^0-0=x；負數: x^(-1)-(-1) = ~x+1 = -x
}
5. 取模/乘除轉位運算（2 的冪次）
| 運算 | 等價位運算 | 條件 |
|---|
a % (2^n) | a & (2^n - 1) | 無符號或正數 |
a * (2^n) | a << n | 無溢出 |
a / (2^n) | a >> n | 無符號或正數(算術右移向下取整) |
補碼運算恆等式速查（配合位運算推導）
-x = ~x + 1 = ~(x - 1)
~x = -x - 1
x + y = (x ^ y) + 2*(x & y) = (x | y) + (x & y)
x - y = (x ^ y) - 2*(~x & y)
x ^ y = (x | y) - (x & y)
實戰宏定義庫
#define SET_BIT(x, n) ((x) |= (1U << (n)))
#define CLEAR_BIT(x, n) ((x) &= ~(1U << (n)))
#define TOGGLE_BIT(x, n) ((x) ^= (1U << (n)))
#define GET_BIT(x, n) (((x) >> (n)) & 1U)
#define ROT_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n))))
#define ROT_RIGHT(x, n) (((x) >> (n)) | ((x) << (32 - (n))))
#define IS_POW2(x) ((x) && !((x) & ((x) - 1)))
#define ABS(x) (((x) ^ ((x) >> 31)) - ((x) >> 31))
#define SWAP(x, y) do { (x) ^= (y); (y) ^= (x); (x) ^= (y); } while(0)
避坑指南
- 移位寬度 ≥ 位寬：C 標準規定行為未定義。
1 << 32 在 32 位 int 上 UB，需用 1ULL << 32。
- 有符號右移：實現定義（通常算術移位），跨平台請用無符號類型配合邏輯右移。
~ 優先級高於算術運算：~x + 1 等價 (~x) + 1，但 ~x * 2 易誤讀，建議加括號。- SWAP 宏參數有副作用：
SWAP(a[i++], b) 會多次求值，嚴禁傳入副作用表達式。
總結
位運算是贴近硬件的高效原語，掌握上述模板可寫出無分支、常數時間、零額外空間的核心邏輯。現代編譯器優化極強，可讀性優先：關鍵熱路徑用位運算並註釋原理，常規業務用清晰的算術/邏輯表達，讓編譯器自動向量化/優化。
