Bit Manipulation
位元操作技巧 - 利用位元運算優化演算法效能。
常見演算法/應用與技巧對照
| 演算法/應用 | 技巧 1 (奇偶) | 技巧 2 (取位) | 技巧 3 (設1) | 技巧 4 (設0) | 技巧 5 (切換) | 技巧 6 (清最右1) | 技巧 7 (取最右1) | 技巧 8 (計數) |
|---|---|---|---|---|---|---|---|---|
| 密碼學 (SHA/MD5) | ✓ | ✓ | ✓ | ✓ | ||||
| IP/子網路遮罩 | ✓ | ✓ | ✓ | ✓ | ||||
| Bloom Filter | ✓ | ✓ | ✓ | |||||
| N 皇后問題 | ✓ | ✓ | ✓ | ✓ | ✓ | |||
| 棋盤遊戲狀態 | ✓ | ✓ | ✓ | ✓ | ||||
| 格雷碼生成 | ✓ | ✓ | ✓ | |||||
| 權限系統 | ✓ | ✓ | ✓ | |||||
| 漢明距離 | ✓ | ✓ | ||||||
| XOR 加密 | ✓ | |||||||
| Fenwick Tree | ✓ | ✓ | ||||||
| Bitmap 操作 | ✓ | ✓ | ✓ | ✓ | ||||
| 壓縮算法 (LZW) | ✓ | ✓ |
基本位元操作技巧
- 判斷奇偶
(n & 1) == 0 - 取得第 i 位
(n >> i) & 1 - 設定第 i 位為 1
n | (1 << i) - 設定第 i 位為 0
n & ^(1 << i) - 切換第 i 位
n ^ (1 << i) - 清除最右邊的 1
n & (n - 1) - 取得最右邊的 1
n & (-n) - 計算二進位中 1 的個數