透過數位邏輯電路學習 Bitwise 操作

為什麼要從邏輯閘學起#

撰寫系統程式時經常會用到位元操作，例如旗標檢查、權限掩碼、低階最佳化。Bitwise 操作其實就是常見邏輯閘的軟體版本，所以本章先快速回顧基礎邏輯閘，再對應到 C 語言中的位元運算子，最後介紹位移與布林函數的實際應用。

邏輯閘#

NOT#

NOT gate 把 1 變成 0、0 變成 1。在積體電路中常用 PMOS + NMOS 組合而成的 CMOS 反相器實作：

if A = Vdd :
    PMOS = cutoff;
    NMOS = on;
    Q = 0v;
if A = 0v :
    PMOS = on;
    NMOS = cutoff;
    Q = Vdd;

真值表：

Input	Output
0	1
1	0

OR#

檢查輸入是否有 1；如果有，就輸出 1，否則為 0。

In1	In2	Out
0	0	0
0	1	1
1	0	1
1	1	1

AND#

邏輯上的兩者相乘，輸入都是 1 時輸出才是 1。

In1	In2	Out
0	0	0
0	1	0
1	0	0
1	1	1

XOR#

互斥或閘：檢查輸入是否相異，若相異輸出 1，否則為 0。

In1	In2	Out
0	0	0
0	1	1
1	0	1
1	1	0

Bitwise 基本操作#

C 語言中的位元運算子，與邏輯閘的功能對應如下。

NOT（`~`）#

int x = 1;
int y = ~x;  // 0

AND（`&`）#

int x = 1;
int y = ~x;       // 0
int z = x & y;    // 0

OR（`|`）#

int x = 1;
int y = ~x;       // 0
int z = x | y;    // 1

XOR（`^`）#

int x = 1;
int y = ~x;       // 0
int z = x ^ y;    // 1

小試身手：判斷 2 的 n 次方#

以 LeetCode 上的 power-of-two ^↗ 為例。

一行版本：

return n > 0 && (n & (n - 1)) == 0;

解題思維：2 的 n 次方無法表示負數，所以輸入值需要大於 0。再來，2 的 n 次方在二進位下只會有一個 bit 為 1，所以 n & (n - 1) 會是 0。

最佳化版本：

bool isPowerOfTwo(int n) {
    if (n == 1) return true;
    if (n & 1) return false;
    return n > 0 && (n & (n - 1)) == 0;
}

最佳化思維：除了 1 以外，奇數不可能是 2 的 n 次方，因此先用 n & 1 判斷是否為奇數可以提早返回。經過這個最佳化，LeetCode 上執行時間可以從 4ms 下降到 0ms。

移位#

「移位」是一個二元運算子，能將二進位數中的每一位向某個方向移動指定位（溢位部分被捨棄），空缺處補 0。在 C 語言中，左移為 <<、右移為 >>。

邏輯左移#

捨棄高位，低位補 0：

1001 << 1 = 0010 (overflow 掉最高位的 1)

邏輯右移#

捨棄低位，高位補 0：

0100 (= 4)
>> 1
= 0010 (= 2)

算術右移#

除了邏輯位移外，還有算術位移（Arithmetic shift）。差別在於：算術右移會在最高位補上符號位（sign bit）的值，以保持正負號正確。

11110 (= -14, 假設 5-bit two's complement)
>> 1 (arithmetic)
= 11111 (= -15, 大致對應到 -14 / 2 取整往下捨入)

在 C 語言中，對於有號數的右移到底是邏輯右移還是算術右移，實際還是要參考編譯器實作。若想在 C 中保證做邏輯右移，可以先把變數轉成無號型別再操作：

int main()
{
    int n = 0xfffffffe;
    int m = (unsigned int)n >> 1;
    printf("0x%x\n", m);
}

那算術左移呢？#

為什麼前面沒有算術左移？

對正數來說（sign-bit = 0）向左移還是正數，若變成負數則代表 overflow。
對負數來說（sign-bit = 1）由於採二補數表示，前面都是 1，若 offset 超過代表該數值有問題。

邏輯左移和算術左移本質上沒有差異，所以一般只談「左移」即可。

移位 ≈ 乘除法#

移位的效果幾乎等效於乘以或除以 2 的次方。對硬體來說，乘除法屬於複雜運算，需要多條指令；若我們熟悉位移操作，便能將原先要多條指令才能做到的事情簡化成一條指令，有助於撰寫更高效的程式碼。

布林函數：用 Bitwise 兜出多工器#

考慮一個二選一的數據多工器（2-to-1 multiplexer），其布林函數可以寫成：

Z = (A AND NOT S) OR (B AND S)

對應到 C 語言：

bool z = (A & ~S) | (B & S);