🔢 Bit Manipulation
位元運算技巧與狀態壓縮。
11 題
📖 分類導讀
位元操作利用二進位的特性高效解題。常用操作包括 AND、OR、XOR、位移等。
Notes:
- XOR 的特性：a ^ a = 0、a ^ 0 = a，常用於找唯一元素
- 位移可以快速實現乘除 2 的冪次
- n & (n - 1) 可以消除最低位的 1
技巧速查
| 目的 | 寫法 |
|---|---|
| 取第 i 位 | (x shr i) and 1 |
| 設第 i 位為 1 | x or (1 shl i) |
| 清除第 i 位 | x and (1 shl i).inv() |
| 翻轉第 i 位 | x xor (1 shl i) |
| 消去最低位的 1 | x and (x - 1) |
| 取出最低位的 1 | x and (-x) |
| 判斷奇偶 | x and 1 |
| 判斷 2 的冪 | x > 0 && (x and (x - 1)) == 0 |
| 計算 1 的個數 | Integer.bitCount(x) |
NOTE
Kotlin 的位元運算用具名中綴函式 and、or、xor、shl、shr、inv()，而非 C/Java 的 & | ^ << >> ~。ushr 是無號右移。
位元向量（bitmap）
用一個整數（或整數陣列）的每個位元當一個布林旗標，能極省空間地表示「集合」或「狀態」：
- 狀態壓縮：用一個
Int的 32 位表示「哪些元素被選」，是狀態壓縮 DP（如旅行推銷員）與子集枚舉的基礎。 - 去重 / 排序：值域有限且不重複時，用 bitmap 一個值一位，掃一遍標記，再從低到高讀出已標記位，即得
O(n)排序兼去重——不需比較。
// 枚舉集合 {0..n-1} 的所有子集：用 mask 的每一位代表「該元素選不選」
fun subsets(nums: IntArray): List<List<Int>> {
val n = nums.size
val res = mutableListOf<List<Int>>()
for (mask in 0 until (1 shl n)) {
val subset = mutableListOf<Int>()
for (i in 0 until n) {
if ((mask shr i) and 1 == 1) subset.add(nums[i])
}
res.add(subset)
}
return res
}TIP
XOR 還能做「不用暫存變數的交換」：a = a xor b; b = a xor b; a = a xor b。面試考點多於實用，但它體現了「用代數性質省空間」的思路。
跨倉庫導讀
- 對應理論章節：位元運算