概述#

Bit manipulation 在各種面試題中都會出現。有時題目明確要求使用位元操作，有時則是優化程式碼的有效手段。你必須能夠用手算和用程式碼操作位元，且要小心不要犯細節錯誤。

Bit Manipulation By Hand#

練習用手算以下位元運算是打好基礎的關鍵。^ 表示 XOR，~ 表示 NOT（取反）。

不確定時，先用十進位思考同樣的運算，再套用到二進位上。

Bit Facts and Tricks#

以下表達式在位元操作中非常實用。不要死背，要理解為什麼它們成立：

x ^ 0s = x        x & 0s = 0        x | 0s = x
x ^ 1s = ~x       x & 1s = x        x | 1s = 1s
x ^ x  = 0        x & x  = x        x | x  = x

這些運算都是 bit-by-bit 獨立進行的，每個位元互不影響。

Two’s Complement and Negative Numbers#

電腦通常使用 Two’s complement（二補數） 來儲存整數：

• 正數以本身表示，最高位（sign bit）為 0
• 負數以其絕對值的二補數表示，最高位為 1

N 位元整數中，-K 的二進位表示為 concat(1, 2^(N-1) - K)。

另一種理解方式：將正數的所有位元取反後加 1，再加上符號位 1。

範例：4 位元整數 -3

• 3 的二進位為 011
• 取反得 100，加 1 得 101
• 加上符號位得 1101

4 位元整數的二補數對照表：

觀察左右兩側的絕對值之和永遠等於 2^3 = 8，且除符號位外二進位值完全相同。

Arithmetic vs. Logical Right Shift#

右移有兩種類型：

Logical Right Shift（邏輯右移）>>>#

• 將位元向右移動，最高位補 0
• 視覺上就是單純的位元右移
• 對 8 位元的 -75（10110101）邏輯右移 1 位，得 01011010 = 90

Arithmetic Right Shift（算術右移）>>#

• 將位元向右移動，最高位補符號位的值（正數補 0，負數補 1）
• 效果相當於除以 2（取整）
• 對 -75（10110101）算術右移 1 位，得 11011010 = -38

int repeatedArithmeticShift(int x, int count) {
    for (int i = 0; i < count; i++) {
        x >>= 1; // Arithmetic shift by 1
    }
    return x;
}

int repeatedLogicalShift(int x, int count) {
    for (int i = 0; i < count; i++) {
        x >>>= 1; // Logical shift by 1
    }
    return x;
}

對 x = -93242，count = 40 執行：

• 邏輯右移：結果為 0（持續將 0 移入最高位）
• 算術右移：結果為 -1（持續將 1 移入最高位，全 1 序列的有號整數為 -1）

Common Bit Tasks: Getting and Setting#

以下操作非常重要，但不要死背。要理解如何實作，這樣才能舉一反三，解決各種位元問題。

Get Bit#

將 1 左移 i 位，得到形如 00010000 的 mask。與 num 做 AND，清除所有其他位元，只保留第 i 位。比較結果是否為 0。

boolean getBit(int num, int i) {
    return ((num & (1 << i)) != 0);
}

Set Bit#

將 1 左移 i 位，得到形如 00010000 的 mask。與 num 做 OR，只會改變第 i 位，其餘位不受影響。

int setBit(int num, int i) {
    return num | (1 << i);
}

Clear Bit#

與 setBit 幾乎相反。先建立 00010000，取反得 11101111，再與 num 做 AND，清除第 i 位。

int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

清除從 MSB 到第 i 位（含）的所有位元：

int clearBitsMSBthroughI(int num, int i) {
    int mask = (1 << i) - 1;
    return num & mask;
}

清除從第 i 位到第 0 位（含）的所有位元：

int clearBitsIthroughO(int num, int i) {
    int mask = (-1 << (i + 1));
    return num & mask;
}

Update Bit#

先用 mask 11101111 清除第 i 位，再將目標值 v 左移 i 位，用 OR 寫入。

int updateBit(int num, int i, boolean bitIs1) {
    int value = bitIs1 ? 1 : 0;
    int mask = ~(1 << i);
    return (num & mask) | (value << i);
}

本章面試題列表#