位元運算（Bit Manipulation）

位元運算（Bit Manipulation） 是直接對整數的二進位表示逐位操作的技巧。對做韌體（firmware）的人來說，這不是「面試才用的花招」，而是每天在讀寫暫存器、拼裝旗標、做記憶體對齊時都會碰到的基本功。這篇用 C 來寫，因為底層工作幾乎都在 C 的世界裡。

面試角度看，位元運算是 Google、NVIDIA、以及所有嵌入式職缺的高頻考點：它考的不只是「你會不會」，還考「你懂不懂機器」。很多陷阱（有號數右移、UB、運算子優先級）就是拿來篩掉「只背過招式、不懂底層」的人。

基本運算

先把六個基本運算釘牢。假設操作的是無號整數：

運算	符號	規則	例子（4-bit）
AND	`&`	兩邊都是 1 才 1	`1100 & 1010 = 1000`
OR	`\|`	有一邊是 1 就 1	`1100 \| 1010 = 1110`
XOR	`^`	兩邊不同才 1	`1100 ^ 1010 = 0110`
NOT	`~`	逐位反轉	`~1100 = 0011`
左移	`<<`	整體往左，右補 0	`0011 << 1 = 0110`
右移	`>>`	整體往右	`0110 >> 1 = 0011`

幾個直覺：

x << n 相當於 x * 2^n（無溢位的前提下）。
無號數的 x >> n 相當於 x / 2^n（往下取整）。
AND 常用來「遮罩取出某些位」，OR 常用來「打開某些位」，XOR 常用來「翻轉某些位」。

set / clear / toggle / test 第 n 個 bit

這四個是韌體操作暫存器的核心慣用語，一定要背到反射：

/* 把第 n 個 bit 設成 1（set） */
x |= (1u << n);

/* 把第 n 個 bit 清成 0（clear） */
x &= ~(1u << n);

/* 把第 n 個 bit 反轉（toggle） */
x ^= (1u << n);

/* 測試第 n 個 bit 是不是 1（test） */
if (x & (1u << n)) { /* 第 n 位是 1 */ }

/* 取出第 n 個 bit 的值（0 或 1） */
int bit = (x >> n) & 1u;

1u << n 產生一個「只有第 n 位是 1」的遮罩（mask），這是所有操作的基礎。~(1u << n) 則是「只有第 n 位是 0、其餘都是 1」，拿來 AND 就能精準清掉那一位而不動到別的位。

用 mask 一次操作多個 bit：韌體裡常見一次設定一整組位。例如要把第 3、4、5 位設 1：

#define FIELD_MASK  (0x7u << 3)   /* 0b0011_1000 */

x |= FIELD_MASK;                  /* 全部設 1 */
x &= ~FIELD_MASK;                 /* 全部清 0 */

/* 把一個欄位寫成特定值 val（先清再寫，避免殘留舊值） */
x = (x & ~FIELD_MASK) | ((val << 3) & FIELD_MASK);

最後那行「先清再寫」是暫存器程式設計的黃金公式：先用 & ~mask 把欄位歸零，再用 | (新值) 填入。少了前半段，舊的位會殘留下來，這是韌體很常見的 bug。

經典招式

這一節是面試最愛考的一組技巧，每一個都值得記住「它為什麼成立」。

`n & (n - 1)`：消掉最低位的 1

n & (n - 1)   /* 把 n 最右邊的那個 1 變成 0 */

原理：n - 1 會把最低位的 1 變成 0，並把它右邊原本的 0 全變成 1。再和 n 做 AND，最低位的 1 之後那些位就全被清掉，最低位的 1 本身也沒了。例如 n = 0b10110，n-1 = 0b10101，n & (n-1) = 0b10100。

判斷 2 的次方：2 的次方只有一個 bit 是 1，消掉它就變 0：

int is_power_of_two(unsigned n) {
    return n != 0 && (n & (n - 1)) == 0;
}

注意 n != 0 不能省——0 也會讓 n & (n-1) == 0 成立，但 0 不是 2 的次方。

`n & -n`：取出最低位的 1

n & -n    /* 只留下 n 最低位的那個 1，其餘清 0 */

原理靠二補數：-n == ~n + 1。~n 把最低位的 1 之後全反轉，+1 進位後，剛好只有原本最低位的 1 那一位在 n 和 -n 裡同時是 1。例如 n = 0b10110，-n = 0b01010，n & -n = 0b00010。這在 Fenwick tree（樹狀陣列）和「找出最低有效位」時很有用。

不用暫存變數 swap

a ^= b;
b ^= a;
a ^= b;

三次 XOR 就交換了 a、b。原理：XOR 有 x ^ x == 0、x ^ 0 == x 的性質。但面試講這招時務必補一句：實務上不要這樣寫。它可讀性差，遇到 a 和 b 是同一個記憶體位址（別名）時會把值變成 0，而且現代編譯器對普通的 tmp swap 早就最佳化得更好。這是「知道但不用」的知識。

XOR 找落單的數

一個陣列裡每個數字都出現兩次，只有一個出現一次，找出它：

int single_number(int *nums, int n) {
    int result = 0;
    for (int i = 0; i < n; i++)
        result ^= nums[i];
    return result;
}

原理同上：成對的數字互相 XOR 抵消成 0，剩下的就是落單的那個。O(n) 時間、O(1) 空間，這是 XOR 最漂亮的應用（LeetCode 136）。

數 set bits（population count）

最直覺的寫法是逐位檢查，O(位寬)。但用 n & (n-1) 可以只跑「1 的個數」那麼多次：

/* Brian Kernighan 演算法：迴圈次數 = set bit 的數量 */
int count_bits(unsigned n) {
    int count = 0;
    while (n) {
        n &= (n - 1);   /* 每次消掉一個最低位的 1 */
        count++;
    }
    return count;
}

實務上直接用編譯器內建函式最快，很多 CPU 有專用指令（x86 的 POPCNT、ARM 的 CNT）：

int c = __builtin_popcount(x);      /* unsigned int */
int cl = __builtin_popcountl(x);    /* unsigned long */

面試時能講出「Brian Kernighan 是 O(set bits)、硬體有 POPCNT 指令、GCC/Clang 提供 __builtin_popcount」會很加分。

round up 到 2 的次方

韌體做記憶體對齊、配置 buffer 時常要「無條件進位到最近的 2 的次方」：

uint32_t round_up_pow2(uint32_t n) {
    if (n == 0) return 1;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

原理：先 n--，然後一連串「右移後 OR 回自己」會把最高位 1 以下的所有位都填成 1，最後 +1 進位成一個乾淨的 2 的次方。這招叫做「bit smearing」。

對齊到任意 2 的次方 A（A 必為 2 的次方），是韌體最常用的公式：

/* 把 addr 無條件進位對齊到 A（A 是 2 的次方） */
#define ALIGN_UP(addr, A)   (((addr) + (A) - 1) & ~((A) - 1))

/* 對齊到下方 */
#define ALIGN_DOWN(addr, A) ((addr) & ~((A) - 1))

/* 檢查是否已對齊 */
#define IS_ALIGNED(addr, A) (((addr) & ((A) - 1)) == 0)

A - 1 是 A 以下全 1 的遮罩（因為 A 是 2 的次方），& ~(A-1) 就把低位全清掉，達成向下對齊。

Firmware 應用

前面的招式在韌體裡的具體樣貌：

暫存器 set / clear / toggle bit：控制硬體就是在讀寫 memory-mapped register 的個別位。慣用寫法：
```
volatile uint32_t *REG = (uint32_t *)0x40021000;
*REG |= (1u << ENABLE_BIT);     /* 開啟某功能 */
*REG &= ~(1u << ENABLE_BIT);    /* 關閉 */
```
注意 volatile——編譯器不能把對硬體暫存器的讀寫最佳化掉。

flag 集合：用一個整數的每個 bit 代表一個布林旗標，省空間又能一次比對多個。

#define FLAG_READY   (1u << 0)
#define FLAG_ERROR   (1u << 1)
#define FLAG_BUSY    (1u << 2)

status |= FLAG_READY;                        /* 設定 */
if (status & FLAG_ERROR) { /* ... */ }        /* 檢查單一 */
if (status & (FLAG_READY | FLAG_BUSY)) { }    /* 檢查任一 */

記憶體對齊：DMA、cache line、page 邊界都要求位址對齊，用上面的 ALIGN_UP / IS_ALIGNED 巨集處理。判斷一個位址是否對齊到 cache line（例如 64 bytes）就是 (addr & 63) == 0。

面試角度與陷阱

這一節是最容易在面試「翻車」的地方，每一條都是 firmware / NVIDIA 面試官會刻意設的坑。

1. 有號數右移是「算術移位」。 對有號負數 x >> n，多數平台會做算術右移（左邊補符號位 1），而不是補 0。這在 C 標準裡其實是 implementation-defined 行為。做位元操作時一律用 unsigned，才有明確定義的邏輯移位（補 0）。

2. 移位量 >= 型別位寬是未定義行為（UB）。 對 32-bit 的 int，1 << 32 是 UB，不保證等於 0。編譯器可能給出任何結果。要移滿整個寬度時要特別小心邊界。

3. 1 << n 對 32 位型別可能溢位。 如果 n 可能到 31 而你在 32-bit int 上做 1 << 31，那是往符號位塞 1，是 UB。永遠寫 1u << n（或 1ul / 1ull），讓字面常數是無號、夠寬。

4. 運算子優先級：&、\|、^ 比 ==、!= 低。 這是位元運算最惡名昭彰的陷阱：

if (x & MASK == 0)    /* 錯！等價於 x & (MASK == 0) */
if ((x & MASK) == 0)  /* 對，一定要加括號 */

== 會先算，於是 MASK == 0 先變成 0 或 1，整個判斷完全走鐘。位元運算子和比較運算子放一起，永遠加括號。

5. 別把邏輯運算子和位元運算子搞混。 && / || 是邏輯（有短路），& / | 是位元（無短路、對每一位運算）。if (a & b) 和 if (a && b) 在某些值下結果不同，而且 & 不會短路，右邊一定會被求值。

6. ~ 的型別提升。 ~0 在 int 是 0xFFFFFFFF（即 -1），做遮罩時要留意結果被提升成 int 可能帶符號，賦值給更寬的型別時會符號延伸。需要固定寬度就用 ~0u、UINT32_MAX 之類。

LeetCode 對照

191. Number of 1 Bits — 數 set bits，練 Brian Kernighan。
136. Single Number — XOR 找落單的數，最經典的 XOR 應用。
231. Power of Two — n & (n-1) == 0 判 2 的次方。
338. Counting Bits — 對 0..n 每個數算 set bits，可用 DP 遞推 bits[i] = bits[i >> 1] + (i & 1)。
260. Single Number III — 進階：兩個數各出現一次，其餘成對。先全部 XOR 得到兩數的 XOR，再用 x & -x 取最低位 1 當「分組依據」把兩群分開。

這五題把本篇的招式都串起來了：練完，位元運算的手感就穩了。

基本運算​

set / clear / toggle / test 第 n 個 bit​

經典招式​

n & (n - 1)：消掉最低位的 1​

n & -n：取出最低位的 1​

不用暫存變數 swap​

XOR 找落單的數​

數 set bits（population count）​

round up 到 2 的次方​

Firmware 應用​

面試角度與陷阱​

LeetCode 對照​