位元運算是 C 貼近硬體的招牌能力：驅動程式的暫存器操作、網路協定的欄位打包、 權限旗標、雜湊函式、壓縮與加密，處處都是位元運算。本單元對應 K&R §2.9， 從六個運算子出發，系統整理遮罩、位移、欄位擷取，以及一批面試與實務都常見的位元技巧。

學習目標

  • 熟練六個位元運算子：&、|、^、~、<<、>>
  • 會用遮罩（mask）設定、清除、切換、測試特定位元
  • 理解位移與 2 的冪次乘除的關係，會用位移擷取欄位（K&R getbits）
  • 掌握常見位元技巧：popcount、判斷 2 的冪、XOR 交換、位元旗標模式
  • 能寫程式檢測機器的位元組序（endianness）
  • 知道位元運算的未定義行為地雷（負數位移、過量位移）

對照章節 / 參考來源

  • K&R §2.9 Bitwise Operators（getbits 範例）
  • C11 標準 §6.5.7（位移運算子）、§6.5.10–6.5.12（AND/XOR/OR）
  • 《Hacker's Delight》(Henry S. Warren)：位元技巧的百科全書
  • Bit Twiddling Hacks（Sean Eron Anderson）

觀念講解

1. 六個運算子複習

運算子 名稱 例（8 位元） 用途
& AND 0b1100 & 0b1010 = 0b1000 取交集、清除位元、取遮罩內欄位
\| OR 0b1100 \| 0b1010 = 0b1110 取聯集、設定位元
^ XOR 0b1100 ^ 0b1010 = 0b0110 切換位元、比較差異、同值歸零
~ NOT（一補數） ~0b0001 = 0b1110 反轉全部位元、製作反遮罩
<< 左移 0b0011 << 2 = 0b1100 乘 2 的冪、製作遮罩
>> 右移 0b1100 >> 2 = 0b0011 除 2 的冪、對齊欄位

注意 &&/|| 是邏輯運算子，&/| 才是位元運算子；^ 沒有邏輯版本。 位元運算的優先權低於比較運算子：x & 1 == 0 其實是 x & (1 == 0)，務必加括號。

2. 遮罩四式：設定 / 清除 / 切換 / 測試

以「第 n 位」（bit 0 為最低位）為例：

x |=  (1u << n);      /* set    ：把第 n 位設為 1 */
x &= ~(1u << n);      /* clear  ：把第 n 位清為 0 */
x ^=  (1u << n);      /* toggle ：把第 n 位反轉   */
bit = (x >> n) & 1u;  /* test   ：讀出第 n 位     */

ASCII 圖（set bit 3）：

x        = 0 1 0 0 0 1 0 1
1u << 3  = 0 0 0 0 1 0 0 0
x | mask = 0 1 0 0 1 1 0 1
                  ^ 只有這一位被影響

用 1u 而非 1：1 << 31 在 32 位 int 上是 signed overflow（UB），無號常量才安全。

3. 位移技巧與欄位擷取

  • x << k 等於 x * 2^k；x >> k 對無號數等於 x / 2^k（向下取整）。
  • 負的有號數右移是「實作定義」行為（多數平台是算術右移，但別依賴它做可攜程式）。
  • 製作「低 n 位全 1」的遮罩：(1u << n) - 1，如 n=4 得 0b1111。

K&R §2.9 的 getbits：取出 x 中「從位置 p 開始、往低位數 n 位」的欄位：

/* getbits(x, 4, 3) -> 取出 bit4 bit3 bit2 */
unsigned getbits(unsigned x, int p, int n)
{
    return (x >> (p + 1 - n)) & ~(~0u << n);
}

拆解：x >> (p+1-n) 把欄位平移到最低位；~(~0u << n) 做出低 n 位為 1 的遮罩。 這正是硬體暫存器讀取、網路封包解析的基本功。

4. 實用技巧精選

/* popcount：數 1 的個數（Kernighan 法，每輪消掉最低位的 1） */
int count = 0;
while (x) { x &= x - 1; count++; }

/* 判斷 2 的冪：2 的冪只有一個 1，x & (x-1) 必為 0 */
is_pow2 = x != 0 && (x & (x - 1)) == 0;

/* 取出最低位的 1（isolate lowest set bit） */
lowest = x & -x;                  /* 對無號數等價於 x & (~x + 1) */

/* XOR 交換（不用暫存變數；現代編譯器下無效能優勢，屬教學／面試題） */
a ^= b; b ^= a; a ^= b;

/* 位元旗標（flags）模式：一個整數存多個布林開關 */
enum { F_READ = 1u << 0, F_WRITE = 1u << 1, F_EXEC = 1u << 2 };
perm |= F_READ | F_WRITE;         /* 開兩個旗標 */
if (perm & F_EXEC) { /* ... */ }  /* 測試 */

實務對照：open(path, O_RDWR | O_CREAT | O_TRUNC, 0644) 的第二個參數、 fcntl、mmap、pthread 的屬性旗標，全部都是這個模式。

5. 位元組序（Endianness）檢測

多位元組整數在記憶體中的排列方式：

uint32_t v = 0x01020304;
little-endian (x86, Apple Silicon):  04 03 02 01   （低位元組在低位址）
big-endian    (網路序, SPARC):       01 02 03 04   （高位元組在低位址）

檢測法：用 unsigned char* 檢視整數的第一個位元組（合法：char 指標可以別名任何物件）：

uint32_t v = 1;
int little = *(unsigned char *)&v == 1;

網路程式必須用 htonl/ntohl 系列在主機序與網路序（big-endian）之間轉換。

範例程式

檔案 內容 編譯 / 執行
01_masks_getbits.c 六運算子總覽、遮罩四式、K&R getbits/setbits、二進位印出工具 cc -std=c11 -Wall -Wextra -o out 01_masks_getbits.c && ./out
02_bit_tricks.c popcount 三種寫法、2 的冪、XOR 交換、最低位 1、位元反轉 cc -std=c11 -Wall -Wextra -o out 02_bit_tricks.c && ./out
03_flags_endian.c 位元旗標權限系統實作、endianness 檢測與位元組傾印 cc -std=c11 -Wall -Wextra -o out 03_flags_endian.c && ./out

常見錯誤與陷阱

  1. 優先權：x & 1 == 0 恆為 x & 0 即 0——== 比 & 先算。 位元運算混搭比較時一律加括號：(x & 1) == 0。
  2. 有號數位移的 UB：1 << 31（int 溢位）、負數左移、位移量 ≥ 型別寬度 （如 x << 32 對 32 位 x）都是未定義行為。遮罩運算一律用無號型別。
  3. ~ 與 ! 混用：!x 是邏輯非（結果 0/1），~x 是位元反轉； if (~x) 幾乎永遠為真（只有 x 全 1 時例外），通常是寫錯。
  4. 右移補位假設：有號負數 >> 是補 0 還是補符號位由實作決定； 要可攜就先轉成無號再移。
  5. XOR 交換自己：swap(&a, &a) 用 XOR 版本會把值清成 0， 泛用函式請用暫存變數版本。

練習題

  1. 【易】寫 print_binary(unsigned x)，用位移與遮罩從最高位印到最低位，不用任何函式庫。
  2. 【易】實作 K&R 習題 2-6 setbits(x, p, n, y)：把 x 中位置 p 起的 n 位換成 y 的低 n 位。
  3. 【中】實作 K&R 習題 2-7 invert(x, p, n)：反轉指定欄位；及 2-8 rightrot(x, n)：循環右移。
  4. 【中】寫一個 RGB565 顏色打包/解包器：把 8 位元 r、g、b 壓進 16 位元 （r 佔 5 位、g 佔 6 位、b 佔 5 位），再解回近似值。
  5. 【難】不用迴圈實作 32 位元 popcount（分治法：先兩兩相加、再四四相加……）。
  6. 【難】實作 next_pow2(uint32_t x)：回傳 ≥ x 的最小 2 的冪 （提示：連續右移 OR：x |= x>>1; x |= x>>2; ...）。

補充：實務場景速寫

硬體暫存器操作（嵌入式的日常）：

#define UART_ENABLE   (1u << 0)
#define UART_PARITY   (1u << 3)
volatile uint32_t *ctrl = (uint32_t *)0x4000C000;   /* memory-mapped 暫存器 */
*ctrl |= UART_ENABLE;                /* 開啟裝置，不動其他位元 */
*ctrl &= ~UART_PARITY;               /* 關掉 parity */

volatile 告訴編譯器每次都真的讀寫記憶體（暫存器可能被硬體改變）， 與位元遮罩是嵌入式開發的固定搭檔。

網路封包欄位打包：IPv4 表頭的 version 與 IHL 擠在同一個位元組， (byte >> 4) & 0xF 取版本、byte & 0xF 取表頭長度——就是 getbits。

權限與旗標：Unix 的 st_mode（檔案型別 + 9 個權限位）、 open 的 O_*、mmap 的 PROT_*，全是本單元的旗標模式。

編譯器內建函式：手寫 popcount 是為了理解原理； 生產程式直接用 __builtin_popcount(x)、__builtin_clz(x)（前導零）、 __builtin_ctz(x)（尾隨零），編譯器會產生單一機器指令（POPCNT/CLZ）。

延伸閱讀

  • K&R §2.9 與習題 2-6 ~ 2-9
  • 《Hacker's Delight》第 2、5 章（基本技巧與 popcount）
  • Bit Twiddling Hacks
  • GCC/Clang 內建函式：__builtin_popcount、__builtin_clz、__builtin_ctz
  • RFC 1700 / man 3 byteorder（網路位元組序）