位運算口訣速記
清零取反要用與，某位置一可用或
若要取反和交換，輕輕鬆鬆用異或
移位運算核心規則
| 運算子 | 行為 | 備註 |
|---|
<< 左移 | 右補 0，左邊位元捨棄 | 等價乘 2n（無溢出前提） |
>> 右移 | 右邊位元捨棄，左邊：正數補 0，負數視實作定義（算術/邏輯位移） | 等價除 2n（無溢出前提） |
>>> 無符號右移 | 左邊一律補 0 | Java/C# 專有，C/C++ 無此運算子 |
三大基本位運算應用模式
& (按位與) —— 掩碼 mask 中目標位為 0，其餘為 1
- 清零特定位：
x &= ~(1 << k)
- 取指定位值：
(x >> k) & 1
| (按位或) —— 掩碼 mask 中目標位為 1，其餘為 0
^ (按位異或) —— 掩碼 mask 中目標位為 1，其餘為 0
- 翻轉特定位：
x ^= (1 << k)
- 無暫存變數交換：
a ^= b; b ^= a; a ^= b;
補碼運算核心恆等式
-x = ~x + 1 = ~(x - 1)
~x = -x - 1
x + y = (x | y) + (x & y)
x - y = (x | ~y) - (~x & y)
x ^ y = (x | y) - (x & y)
經典實戰技巧速查表
| 功能 | 位運算寫法 | 備註 |
|---|
| 判斷奇偶 | (x & 1) == 1 奇 / == 0 偶 | |
| 取第 k 位 | (x >> k) & 1 | k 從 0 起算 |
| 清第 k 位 | x &= ~(1 << k) | |
| 置第 k 位 | x |= (1 << k) | |
| 循環左移 k | x = (x << k) | (x >> (n-k)) | n 為位寬 |
| 無溢出平均值 | (x & y) + ((x ^ y) >> 1) | 避免 (x+y) 溢出 |
| 判斷 2 的冪 | (x & (x-1)) == 0 && x != 0 | |
| 絕對值 (無分支) | y = x >> 31; return (x ^ y) - y; | 32 位 int |
| 模 2n | x & (2n - 1) | 等價 x % (1<<n) |
| 乘 2n | x << n | |
| 除 2n | x >> n | 負數行為視實作定義 |
進階位元技巧
// 取末 k 位: x & ((1 << k) - 1)
// 末 k 位置 1: x | ((1 << k) - 1)
// 末 k 位翻轉: x ^ ((1 << k) - 1)
// 右側連續 1 變 0: x & (x + 1)
// 右側首個 0 變 1: x | (x + 1)
// 右側連續 0 變 1: x | (x - 1)
// 取右側連續 1: (x ^ (x + 1)) >> 1
// 去掉右起首 1 左側: x & (x ^ (x - 1))
實戰範例：計算區間 [y, x] 間 1 的個數
int countOnesInRange(int x, int y, unsigned short k) {
int cnt = 0;
for (int i = y; i <= x; i++)
cnt += (k >> (i - 1)) & 1;
return cnt;
}
避坑指南
- 右移負數行為為實作定義（Implementation-defined），跨平台需謹慎
- 移位量 ≥ 位寬屬未定義行為
- 有號整數溢出屬未定義行為，無號整數則模 2n 環繞
- 優先使用無號類型進行位運算，避免符號位干擾
