位操作應用#

Number of 1 Bits ^↗#

計算無號整數二進位中 1 的個數（Hamming Weight）。

逐位檢查#

走訪 32 位，用 mask 逐一檢查每位。

fun hammingWeight(n: Int): Int {
    var count = 0
    var mask = 1
    repeat(32) {
        if ((n and mask) != 0) count++
        mask = mask shl 1
    }
    return count
}

時間複雜度：O(32) = O(1)

Brian Kernighan 演算法#

利用 x and (x - 1) 每次消除一個 1。

fun hammingWeight(n: Int): Int {
    var num = n
    var count = 0
    while (num != 0) {
        num = num and (num - 1)
        count++
    }
    return count
}

時間複雜度：O(k)，k 為 1 的個數

對於稀疏位元（1 很少），Brian Kernighan 演算法更高效。例如 1000...0000 只需迴圈 1 次。

Power of Two ^↗#

判斷整數是否為 2 的冪次方。

核心觀察#

2 的冪次方的二進位特點：只有一個 1

2^0 = 1   → 0001
2^1 = 2   → 0010
2^2 = 4   → 0100
2^3 = 8   → 1000

解法#

fun isPowerOfTwo(n: Int): Boolean {
    return n > 0 && (n and (n - 1)) == 0
}

邏輯：

• n > 0：排除負數和 0
• (n and (n - 1)) == 0：只有一個 1 時，消除後為 0

Counting Bits ^↗#

給定 n，返回 0 到 n 每個數的二進位 1 的個數。

動態規劃解法#

利用遞推公式：bits[i] = bits[i and (i - 1)] + 1

fun countBits(n: Int): IntArray {
    val bits = IntArray(n + 1)
    for (i in 1..n) {
        bits[i] = bits[i and (i - 1)] + 1
    }
    return bits
}

原理：i and (i - 1) 的值比 i 小，且 1 的個數恰好少 1。利用已計算的結果推導當前值。

時間複雜度：O(n)

N 皇后的位運算最佳化#

傳統 N 皇后使用集合記錄攻擊範圍，位運算可大幅加速。

核心思想#

用整數的二進位位表示棋盤狀態：

• 0：可放置
• 1：被攻擊

關鍵程式碼#

class NQueens(private val n: Int) {
    private var count = 0

    fun totalNQueens(): Int {
        dfs(0, 0, 0, 0)
        return count
    }

    private fun dfs(row: Int, col: Int, pie: Int, na: Int) {
        if (row >= n) {
            count++
            return
        }

        // 取得當前層所有可放位置（1 表示可放）
        var available = (col or pie or na).inv() and ((1 shl n) - 1)

        while (available != 0) {
            // 取最低位的 1（選一個位置）
            val p = available and -available

            // 遞迴到下一層
            dfs(
                row + 1,
                col or p,            // 列限制
                (pie or p) shl 1,    // 左對角線向左移
                (na or p) shr 1      // 右對角線向右移
            )

            // 處理下一個可用位置
            available = available and (available - 1)
        }
    }
}

複雜度優勢#

位運算解法在面試中能展現亮點，但必須能清楚解釋每一步的含義。死記硬背而無法解釋反而會被扣分。

編碼思維：萬物皆可編碼#

前面幾題都在「操作」既有的位元。但位操作更深的價值，在於提供一種編碼視角：把現實世界的問題，翻譯成二進位的語言。

任何「編號」的方法，本質上都等價於一套二進位編碼——因為每個編號都能寫成二進位。看懂這一點，許多看似要逐一嘗試的現實問題，都能改用「二進位拆分」來優雅解決：把一個大問題，拆成 log₂ 個獨立的「是 / 否」位元。

四個用二進位思維解的經典謎題#

這幾個謎題的共同主角，都是「位權」（1、2、4、8…）與「每個 bit 攜帶 1 bit 資訊」。

分割金條#

要在 7 天內，每天付給工人 1/7 根金條，但只能切兩刀。

• 在 1/7 與 3/7 處各切一刀，得到三段：1、2、4（正是二進位位權 001、010、100）。
• 用「找零」的方式組合，就能湊出 1 ～ 7 任意天數的累計支付：
  • 第 1 天給 1；第 2 天給 2、收回 1；第 3 天再給回 1……以此類推。
• 三段湊出 1 ～ 7，正對應 3 個 bit 能表示 001～111。

小白鼠試毒#

64 瓶藥水裡有 1 瓶有毒，喝下後固定時間發作。要找出毒藥，只需 6 隻小白鼠。

• 把瓶子按 000000～111111 編號（0 ～ 63），每隻小白鼠對應一個 bit。
• 第 k 隻小白鼠，喝下所有「第 k 個 bit 為 1」的瓶子。
• 發作後，把死亡的小白鼠那幾位記為 1，直接讀出來就是毒藥的二進位編號。
• 理論依據：log₂64 = 6，6 個 bit 足以區分 64 種情況。

同樣的編碼技巧也能用在工程上：若有多組互不衝突的 A/B 測試，可以用二進位編碼讓每位使用者同時落入多個實驗，併行而不互相干擾。

兩個玻璃球#

有 1 ～ 100 層樓，玻璃球從某臨界高度以上會摔破。手上只有兩顆球，要用最少次數找出臨界層。

• 把樓層當成「十位 + 個位」的兩段編碼：第一顆球做粗調，第二顆球做精調。
• 先用第一顆球在第 10、20、30… 層試（粗定區間），摔破後改用第二顆從區間底部逐層試（細定）。
• 進一步用「遞減步長」最佳化（14、27、39…）後，最壞情況約 19 次即可定位。

共同點#

三題的本質完全一樣：用 log 級的資訊量，解一個看似需要線性次數的問題。只要能把答案空間「編碼」成獨立的位元，問題的規模就會從線性塌縮成對數。

錯誤更正：用冗餘位元偵錯與糾錯#

資料在傳輸或儲存時可能出錯（位元被翻轉）。解法是刻意加入冗餘位元，讓接收端不只能偵測錯誤，甚至能修正錯誤。

奇偶校驗（parity）#

最簡單的偵錯：對所有資料位元做 XOR，得到 1 個校驗位，使整體 1 的個數為偶數。

• 傳輸後重算 XOR：結果非 0，代表發生了奇數個錯誤。
• 缺點：只能偵測、無法定位，且偵測不到偶數個錯誤。

二維奇偶校驗#

把資料排成方陣，對每一列、每一行各算一個校驗位：

        c0 c1 c2 c3 | 行校驗
  r0     1  0  1  1 |  1
  r1     0  1  1  0 |  0
  r2     1  1  0  0 |  0
  ------------------+-----
  列校驗 0  0  0  1 |

• 若某個位元被翻轉，它所在的那一列和那一行的校驗位會同時不匹配。
• 不匹配的列 × 不匹配的行，交叉點就是出錯的位置——找到位置後，把該位元翻回去即完成糾錯。

這正是 RAID（磁碟陣列容錯）、CD/DVD 糾錯碼的思想原型。

壓縮與糾錯是一體兩面：壓縮是「移除冗餘」，把資料壓到最短；糾錯碼是「加入冗餘」，用額外位元換取對抗錯誤的能力。兩者都圍繞著同一個核心量——資訊量。

練習題目#