練習題與詳解 — 位元運算技巧

本檔收錄 5 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住再看「解題思路」，寫完對照「參考解答」。每題完整程式碼在 exercises/：

cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_print_binary.c && /tmp/out

貫穿本單元的三個基本功：遮罩製造（~(~0u << n) 得低 n 個 1）、 平移定位（mask << shift 移到目標欄位）、 三大操作（| 設位、& ~ 清位、^ 翻位）。

練習 1：print_binary（難度：基礎）

題目

寫 void print_binary(unsigned x)：用位移與遮罩從最高位印到最低位，不用任何函式庫轉換函式。要求每 4 位插一個空白（nibble 分組），且位元寬度不寫死 32（用 sizeof 與 CHAR_BIT 計算）。

測資需含：0、1、5、0xFF、0xDEADBEEF、1u<<31、UINT_MAX。

解題思路

取出第 i 位：(x >> i) & 1u——把目標位右移到最低位，再用 & 1 遮掉其他位。這一式是所有位元檢查的原子操作。
從高到低：印出順序要 MSB 先，所以 i 從 nbits-1 遞減到 0。寬度 nbits = sizeof x * CHAR_BIT（CHAR_BIT 在 <limits.h>，幾乎所有平台是 8，但寫出來才是可攜的習慣）。
為什麼用 unsigned：有號數右移負值是實作定義行為，位元操作一律用無號型別，這是本單元的鐵律。
nibble 分組：i % 4 == 0 時（且非最後一位）補空白—— 4 位恰是一個十六進位數字，人眼對照 hex 輸出時特別方便。
邊界測資：1u << 31（只有最高位）驗證沒有把最高位漏掉或算錯符號；UINT_MAX（全 1）驗證每一位都掃到。

參考解答

/*
 * ex1_print_binary.c — 練習 1：print_binary（純位移與遮罩）
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_print_binary.c
 * 執行：/tmp/out
 *
 * 用位移與遮罩從最高位印到最低位，不用任何函式庫轉換函式。
 * 每 4 位插一個空白方便閱讀（nibble 分組）。
 */
#include <stdio.h>
#include <limits.h>     /* CHAR_BIT */

/*
 * 從 MSB 掃到 LSB：把「第 i 位」右移到最低位再 & 1。
 * 位元寬度用 sizeof(x) * CHAR_BIT 算，不寫死 32。
 */
static void print_binary(unsigned x)
{
    int nbits = (int)(sizeof x * CHAR_BIT);

    for (int i = nbits - 1; i >= 0; i--) {
        putchar(((x >> i) & 1u) ? '1' : '0');
        if (i % 4 == 0 && i != 0)
            putchar(' ');               /* 每 4 位一組 */
    }
}

static void show(unsigned x)
{
    printf("  %10u = 0x%08X = ", x, x);
    print_binary(x);
    putchar('\n');
}

int main(void)
{
    printf("print_binary(unsigned) -- MSB first, nibble groups:\n\n");

    show(0u);
    show(1u);
    show(5u);
    show(0xFFu);
    show(0xDEADBEEFu);
    show(1u << 31);
    show(UINT_MAX);                     /* 全 1：驗證最高位沒漏 */
    return 0;
}

程式碼講解

(x >> i) & 1u 中的 1u：跟無號的 x 運算，全程停留在無號世界。
迴圈變數 i 同時扮演「位索引」與「分組計數」兩個角色： i % 4 == 0 表示剛印完一組 4 位。
show 同時印十進位、十六進位、二進位三種表示： 0xDEADBEEF 那行可以逐 nibble 對照 D=1101、E=1110…，自我驗證輸出正確。
易錯處：迴圈寫成 i > 0 會漏印最低位；或把分組條件寫成 i % 4 == 3 導致空白位置錯亂。

範例輸出

print_binary(unsigned) -- MSB first, nibble groups:

           0 = 0x00000000 = 0000 0000 0000 0000 0000 0000 0000 0000
           1 = 0x00000001 = 0000 0000 0000 0000 0000 0000 0000 0001
           5 = 0x00000005 = 0000 0000 0000 0000 0000 0000 0000 0101
         255 = 0x000000FF = 0000 0000 0000 0000 0000 0000 1111 1111
  3735928559 = 0xDEADBEEF = 1101 1110 1010 1101 1011 1110 1110 1111
  2147483648 = 0x80000000 = 1000 0000 0000 0000 0000 0000 0000 0000
  4294967295 = 0xFFFFFFFF = 1111 1111 1111 1111 1111 1111 1111 1111

練習 2：setbits（K&R 2-6）（難度：基礎）

題目

實作 K&R 習題 2-6：

unsigned setbits(unsigned x, int p, int n, unsigned y);

回傳 x，但「從位置 p 起往右數 n 位」（即 bit p 到 bit p-n+1）換成 y 的最低 n 位，其餘位元不變。

測資：setbits(0xAA, 4, 3, 0x07) 應得 0xBE；並須驗證「y 的高位垃圾會被擋掉」（y=0xFF 只取低 2 位）。

解題思路

拆解需求：結果 = （x 把欄位挖空）OR（y 的低 n 位放進欄位）。兩個半成品各自做好再合併。
造遮罩——本單元最重要的慣用式：

~0u        = 1111 1111   全 1
~0u << n   = 1111 1000   低 n 位變 0（n=3）
~(~0u<<n)  = 0000 0111   恰好 n 個 1

平移到欄位：欄位最右位的索引是 p+1-n （K&R 的 p 是欄位「最左位」……不對，是「最右位＋n−1」；換句話說欄位佔 bit p 到 bit p-n+1），所以 field = mask << (p+1-n)。
組裝： - 挖空：x & ~field； - 填入：(y & mask) << (p+1-n)——先 & mask 擋掉 y 的高位，再平移； - 合併：兩者 OR。
手算驗證（測資 1）：x=1010 1010，p=4、n=3 → 欄位 bit 4..2。挖空 → 1010 0010；y 低 3 位 = 111，平移 2 → 0001 1100； OR → 1011 1110 = 0xBE。✓

參考解答

/*
 * ex2_setbits.c — 練習 2：K&R 習題 2-6 setbits(x, p, n, y)
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_setbits.c
 * 執行：/tmp/out
 *
 * setbits(x,p,n,y)：回傳 x，但「從位置 p 起往右數 n 位」換成
 * y 的最低 n 位，其餘位元不變。
 * 位置慣例（同 K&R getbits）：p 是欄位「最右位」的索引 + n - 1，
 * 即欄位佔據 bit p, p-1, ..., p-n+1。
 */
#include <stdio.h>

/* 印 8 位二進位（本題數值小，8 位夠看） */
static void print8(unsigned x)
{
    for (int i = 7; i >= 0; i--)
        putchar(((x >> i) & 1u) ? '1' : '0');
}

/*
 * 推導：
 *   mask = ~(~0u << n) 是「低 n 位全 1」：
 *       ~0u      = 111...111
 *       ~0u << n = 111...000（低 n 位變 0）
 *       再取反   = 000...111（恰好 n 個 1）
 *   欄位遮罩 = mask << (p+1-n)：把 n 個 1 平移到欄位位置。
 *   步驟：
 *     1. x & ~(mask << (p+1-n))   把 x 的欄位清 0
 *     2. (y & mask) << (p+1-n)    取 y 低 n 位並平移到欄位位置
 *     3. 兩者 OR
 */
static unsigned setbits(unsigned x, int p, int n, unsigned y)
{
    unsigned mask = ~(~0u << n);            /* 低 n 位全 1 */
    unsigned field = mask << (p + 1 - n);   /* 平移到目標欄位 */

    return (x & ~field) | ((y & mask) << (p + 1 - n));
}

static void demo(unsigned x, int p, int n, unsigned y)
{
    unsigned r = setbits(x, p, n, y);

    printf("  setbits(x=");
    print8(x);
    printf(", p=%d, n=%d, y=", p, n);
    print8(y);
    printf(")\n    = ");
    print8(r);
    printf("  (0x%02X)\n", r);
}

int main(void)
{
    printf("setbits(x, p, n, y): replace n bits of x at position p\n");
    printf("with the low n bits of y  (bit p..p-n+1)\n\n");

    /* x = 1010 1010，把 bit 4..2 換成 y=...111 的低 3 位 */
    demo(0xAAu, 4, 3, 0x07u);

    /* x 全 1，把 bit 7..4 換成 y 低 4 位 = 0000 */
    demo(0xFFu, 7, 4, 0x00u);

    /* x 全 0，把 bit 5..5（單一位）設成 1 */
    demo(0x00u, 5, 1, 0x01u);

    /* y 的高位垃圾必須被 mask 擋掉：y=0xFF 但只取低 2 位 */
    demo(0x00u, 3, 2, 0xFFu);
    return 0;
}

程式碼講解

三步驟各自對應一個位元操作角色：& ~field 清位、 & mask 篩選、| 合併——把口訣寫進程式結構裡。
最後一組測資是防禦性檢查：若忘了 y & mask，y=0xFF 的高位會污染欄位以外的位元（結果會是 0x3C 而非 0x0C）。
~0u 一定要帶 u：~0 是有號 int 的 -1，左移有號負值牽涉未定義／實作定義行為。
易錯處：位置慣例。K&R 的 p 指欄位最高位索引，平移量是 p+1-n 而不是 p；把 demo(0xAA,4,3,...) 的欄位畫在紙上（bit 4、3、2）再對答案最保險。

範例輸出

setbits(x, p, n, y): replace n bits of x at position p
with the low n bits of y  (bit p..p-n+1)

  setbits(x=10101010, p=4, n=3, y=00000111)
    = 10111110  (0xBE)
  setbits(x=11111111, p=7, n=4, y=00000000)
    = 00001111  (0x0F)
  setbits(x=00000000, p=5, n=1, y=00000001)
    = 00100000  (0x20)
  setbits(x=00000000, p=3, n=2, y=11111111)
    = 00001100  (0x0C)

練習 3：invert 與 rightrot（K&R 2-7、2-8）（難度：進階）

題目

實作兩個函式：

unsigned invert(unsigned x, int p, int n)：把 x 中位置 p 起的 n 位反轉（1→0、0→1），其餘不變；
unsigned rightrot(unsigned x, int n)：把 x 循環右移 n 位（移出的位元從最高位補回），n 可以超過位元寬度、可以是 0。

驗收：invert 做兩次要還原；rightrot 32 次每次 1 位要還原； rightrot(x, 36) 要等於 rightrot(x, 4)。

解題思路

invert：認出這是 XOR。三大操作的分工——設位用 |、清位用 & ~、翻位用 ^。與 1 XOR 翻轉、與 0 XOR 不變，所以「只翻欄位」= 把欄位遮罩 XOR 上去，一行解決：

return x ^ (~(~0u << n) << (p + 1 - n));

遮罩製造與練習 2 完全相同——基本功的複利。 2. invert 的自我驗證：XOR 是對合（involution），做兩次還原。這性質讓測試不需要手算答案。 3. rightrot 的分解：循環 = 平移 + 接回。 - 右移後低 n 位掉出去：先用 x & ~(~0u << n) 把它們存下來； - 掉出去的要接到最高位：左移 寬度 - n； - 兩半 OR。 4. 兩個邊界陷阱（本題真正的考點）： - n 大於寬度：先 n %= w（轉 36 位 = 轉 4 位）； - 取模後 n == 0：low << (w - 0) 是 移位量等於寬度的未定義行為，必須特判直接回傳 x。 5. 驗收設計：轉 32 次 × 1 位應還原（不丟位元）、 36 與 4 等價（取模）、32 位不變（整圈）。

參考解答

/*
 * ex3_invert_rightrot.c — 練習 3：K&R 習題 2-7 invert 與 2-8 rightrot
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_invert_rightrot.c
 * 執行：/tmp/out
 *
 * invert(x,p,n)：把 x 中位置 p 起的 n 位反轉（1變0、0變1），其餘不變。
 * rightrot(x,n)：把 x 循環右移 n 位（移出的位元從最高位補回）。
 */
#include <stdio.h>
#include <limits.h>

static void print8(unsigned x)
{
    for (int i = 7; i >= 0; i--)
        putchar(((x >> i) & 1u) ? '1' : '0');
}

/*
 * invert：XOR 的教科書應用。
 * 與 1 做 XOR 會翻轉、與 0 做 XOR 保持不變——
 * 所以「欄位遮罩」XOR 上去就是「只翻欄位」。
 */
static unsigned invert(unsigned x, int p, int n)
{
    unsigned mask = ~(~0u << n) << (p + 1 - n);   /* 欄位處全 1 */
    return x ^ mask;
}

/*
 * rightrot：右移 n 位後，把「掉出去的低 n 位」貼回最高位。
 *   低 n 位   = x & ~(~0u << n)
 *   貼回位置 = 左移 (寬度 - n)
 * 邊界：n 可能大於寬度，先取模；n == 0 時 << width 是 UB，要特判。
 */
static unsigned rightrot(unsigned x, int n)
{
    int w = (int)(sizeof x * CHAR_BIT);

    n %= w;
    if (n == 0)
        return x;                       /* 避免 x << w 的未定義行為 */

    unsigned low = x & ~(~0u << n);     /* 會被移出的低 n 位 */
    return (x >> n) | (low << (w - n));
}

int main(void)
{
    printf("=== invert(x, p, n): flip n bits at position p ===\n\n");

    unsigned x = 0xAAu;                 /* 1010 1010 */
    printf("  x            = ");
    print8(x);
    printf("\n");

    printf("  invert(x,4,3)= ");
    print8(invert(x, 4, 3));            /* 翻 bit 4..2 */
    printf("  (flip bits 4..2)\n");

    printf("  invert(x,7,8)= ");
    print8(invert(x, 7, 8));            /* 翻全部 = ~x 的低 8 位效果 */
    printf("  (flip all 8 bits)\n");

    /* 翻兩次應該還原 */
    printf("  twice        = ");
    print8(invert(invert(x, 4, 3), 4, 3));
    printf("  (involution: back to x)\n");

    printf("\n=== rightrot(x, n): rotate right ===\n\n");

    unsigned y = 0x000000FFu;
    printf("  y             = 0x%08X\n", y);
    printf("  rightrot(y,4) = 0x%08X  (F wraps to top)\n", rightrot(y, 4));
    printf("  rightrot(y,8) = 0x%08X\n", rightrot(y, 8));
    printf("  rightrot(y,32)= 0x%08X  (full turn: unchanged)\n",
           rightrot(y, 32));
    printf("  rightrot(y,36)= 0x%08X  (36 mod 32 = 4)\n", rightrot(y, 36));

    /* 旋轉不丟位元：轉 32 次每次 1 位應還原 */
    unsigned z = 0xDEADBEEFu;
    unsigned r = z;
    for (int i = 0; i < 32; i++)
        r = rightrot(r, 1);
    printf("\n  rotate 0x%08X by 1, 32 times -> 0x%08X (%s)\n",
           z, r, r == z ? "restored" : "BUG");
    return 0;
}

程式碼講解

invert 本體一行——當你發現需求是「有條件的翻轉」，直覺就該指向 XOR。它同時是加密（one-time pad）、 swap 技巧、同位檢查的基礎。
rightrot 的 n %= w; if (n == 0) return x; 兩行是整題最貴的兩行：漏掉前者，rightrot(y,36) 直接 UB（移位量 ≥ 寬度）；漏掉後者，n=0 或 32 的倍數時 low << 32 也是 UB。 移位量必須嚴格小於位元寬度是 C 移位運算的硬規定。
主程式的三個驗證（對合、整圈、取模等價）都是「不需要手算預期值」的性質測試——為位元程式設計測試時的好模式。
易錯處：把「循環右移」寫成算術右移（有號數右移補符號位）；全程用 unsigned 便沒有這個問題。

範例輸出

=== invert(x, p, n): flip n bits at position p ===

  x            = 10101010
  invert(x,4,3)= 10110110  (flip bits 4..2)
  invert(x,7,8)= 01010101  (flip all 8 bits)
  twice        = 10101010  (involution: back to x)

=== rightrot(x, n): rotate right ===

  y             = 0x000000FF
  rightrot(y,4) = 0xF000000F  (F wraps to top)
  rightrot(y,8) = 0xFF000000
  rightrot(y,32)= 0x000000FF  (full turn: unchanged)
  rightrot(y,36)= 0xF000000F  (36 mod 32 = 4)

  rotate 0xDEADBEEF by 1, 32 times -> 0xDEADBEEF (restored)

練習 4：RGB565 顏色打包／解包（難度：進階）

題目

寫一個 RGB565 顏色打包／解包器：把 8 位元的 r、g、b 壓進 16 位元（r 佔 5 位、g 佔 6 位、b 佔 5 位），再解回 8 位元近似值。要求：

印出打包後的 16 位元值與解包後的近似值、以及每個通道的誤差；
純黑、純白、三原色的解包結果必須精確（誤差 0）—— 這需要正確的解包技巧，天真的補零做不到。

解題思路

佈局先畫圖：

bit 15........11 10..........5 4...........0
    r r r r r    g g g g g g   b b b b b

綠色拿 6 位不是隨便分的：人眼對綠色最敏感，多給一位誤差減半。 2. 打包 = 量化 + 平移 + 合併： - 量化：8 位 → 5 位就是丟掉低 3 位（r >> 3）； - 平移：r 的 5 位放 bit 15..11（<< 11）、g 放 bit 10..5 （<< 5）、b 放 bit 4..0； - 合併：三段互不重疊，OR 起來。 3. 解包的陷阱：取出 5 位後天真地 << 3 低位補 0，最大值 31 只能還原成 11111000 = 248——純白變灰白。 4. 位元複製（bit replication）：左移後用自己的高位補低位：

r5 = abcde
r8 = abcde|abc  即 (r5 << 3) | (r5 >> 2)

如此 0 → 0、31 → 255，兩端精確、中間誤差平均分布。這是所有影像函式庫的標準做法。 5. 驗收設計：黑、白、三原色誤差必為 0（位元複製的保證）；中間值（gray、orange）有小誤差是量化的本質，印出來觀察量級（5 位通道最多 ±4、6 位通道最多 ±2）。

參考解答

/*
 * ex4_rgb565.c — 練習 4：RGB565 顏色打包／解包器
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_rgb565.c
 * 執行：/tmp/out
 *
 * 把 8 位元的 r、g、b 壓進 16 位元（r 佔 5 位、g 佔 6 位、b 佔 5 位），
 * 再解回 8 位元近似值。這是嵌入式 LCD 與早期遊戲機的標準像素格式。
 *
 * 佈局：
 *   bit 15........11 10..........5 4...........0
 *       r r r r r    g g g g g g   b b b b b
 */
#include <stdio.h>
#include <stdint.h>

/*
 * 打包：8 位 -> 5/6/5 位。
 * 量化：直接右移丟掉低位（r>>3 保留高 5 位）。
 * 平移：r 放 bit 15..11、g 放 bit 10..5、b 放 bit 4..0。
 */
static uint16_t rgb565_pack(uint8_t r, uint8_t g, uint8_t b)
{
    return (uint16_t)(((r >> 3) << 11) | ((g >> 2) << 5) | (b >> 3));
}

/*
 * 解包：5/6/5 位 -> 8 位近似值。
 * 天真做法（<<3 低位補 0）會讓最大值變 0xF8 而非 0xFF；
 * 標準技巧「位元複製」：左移後用自己的高位補低位，
 * 讓 0 -> 0、最大 -> 0xFF，誤差平均分布。
 *   r8 = (r5 << 3) | (r5 >> 2)   （5 位：補 3 位，取高 3 位）
 *   g8 = (g6 << 2) | (g6 >> 4)   （6 位：補 2 位，取高 2 位）
 */
static void rgb565_unpack(uint16_t c, uint8_t *r, uint8_t *g, uint8_t *b)
{
    unsigned r5 = (c >> 11) & 0x1Fu;    /* 高 5 位 */
    unsigned g6 = (c >> 5)  & 0x3Fu;    /* 中 6 位 */
    unsigned b5 = c & 0x1Fu;            /* 低 5 位 */

    *r = (uint8_t)((r5 << 3) | (r5 >> 2));
    *g = (uint8_t)((g6 << 2) | (g6 >> 4));
    *b = (uint8_t)((b5 << 3) | (b5 >> 2));
}

static void demo(const char *name, uint8_t r, uint8_t g, uint8_t b)
{
    uint16_t packed = rgb565_pack(r, g, b);
    uint8_t r2, g2, b2;

    rgb565_unpack(packed, &r2, &g2, &b2);
    printf("  %-7s (%3u,%3u,%3u) -> 0x%04X -> (%3u,%3u,%3u)"
           "  err=(%+d,%+d,%+d)\n",
           name, r, g, b, packed, r2, g2, b2,
           r2 - r, g2 - g, b2 - b);
}

int main(void)
{
    printf("RGB888 -> RGB565 (5/6/5 bits) -> RGB888 approximation:\n\n");

    demo("black",  0,   0,   0);
    demo("white",  255, 255, 255);      /* 位元複製讓它精確回 255 */
    demo("red",    255, 0,   0);
    demo("green",  0,   255, 0);
    demo("blue",   0,   0,   255);
    demo("orange", 255, 165, 0);
    demo("gray",   128, 128, 128);
    demo("teal",   0,   128, 128);

    /* 綠色多一位的理由：人眼對綠最敏感，6 位誤差減半 */
    printf("\nnote: green gets 6 bits (human eyes are most sensitive\n");
    printf("to green), so its max error is half of red/blue.\n");
    return 0;
}

程式碼講解

rgb565_pack 一行完成：三個通道各自「量化→平移」後 OR。注意整個運算式最後 cast 回 uint16_t——中間計算在 int 世界進行（整數提升），最後才收窄。
解包的 & 0x1Fu／& 0x3Fu：取欄位時永遠先遮罩，即使你「知道」高位是 0——這是 getbits 模式的紀律。
位元複製 (r5 << 3) | (r5 >> 2) 的妙處：把 5 位值視為「0 到 1 之間的分數」，複製高位等於乘上 255/31 的近似—— 兩端精確、單調遞增。
輸出的 err= 欄讓量化誤差可見：5 位通道 gray 誤差 +4、 6 位通道只 +2，正是「多一位、誤差減半」的實證。
易錯處：解包時把 g 的遮罩寫成 0x1F（5 位）——green 通道是 6 位，遮罩 0x3F；欄位寬度不一致是 565 格式最常見的 bug。

範例輸出

RGB888 -> RGB565 (5/6/5 bits) -> RGB888 approximation:

  black   (  0,  0,  0) -> 0x0000 -> (  0,  0,  0)  err=(+0,+0,+0)
  white   (255,255,255) -> 0xFFFF -> (255,255,255)  err=(+0,+0,+0)
  red     (255,  0,  0) -> 0xF800 -> (255,  0,  0)  err=(+0,+0,+0)
  green   (  0,255,  0) -> 0x07E0 -> (  0,255,  0)  err=(+0,+0,+0)
  blue    (  0,  0,255) -> 0x001F -> (  0,  0,255)  err=(+0,+0,+0)
  orange  (255,165,  0) -> 0xFD20 -> (255,166,  0)  err=(+0,+1,+0)
  gray    (128,128,128) -> 0x8410 -> (132,130,132)  err=(+4,+2,+4)
  teal    (  0,128,128) -> 0x0410 -> (  0,130,132)  err=(+0,+2,+4)

note: green gets 6 bits (human eyes are most sensitive
to green), so its max error is half of red/blue.

練習 5：無迴圈 popcount 與 next_pow2（難度：挑戰）

題目

不用迴圈實作兩個函式，並各自用笨方法（或 builtin）驗證：

int popcount32(uint32_t x)：數 x 中 1 的個數（分治法，5 步）；
uint32_t next_pow2(uint32_t x)：回傳 ≥ x 的最小 2 的冪（next_pow2(17)=32、next_pow2(16)=16、next_pow2(0)=1）。

解題思路

popcount 分治法：

逐位數是 O(位元數) 的迴圈；分治的洞見是平行處理：把 32 位當成 16 組「2 位小加法器」同時運算。
第一步：每 2 位一組，組內兩位相加（結果 0..2，2 位存得下）。遮罩 0x55555555（0101…）取偶數位：

x        = ab ab ab ...（每組 2 位）
x & 0x55 =  b  b  b ...（低位）
(x>>1)&0x55 = a a a ...（高位）
相加     = 每組的 1 數

實戰版 x - ((x>>1) & 0x5555…) 是等價的省指令寫法：對每組 ab，ab - a 恰好是該組 1 的個數（枚舉四種情況可證）。 3. 之後每步把組寬加倍：4 位組（遮罩 0x33333333）、8 位組（0x0F0F0F0F）、16、32——log₂(32) = 5 步定案。後面幾步組寬夠大不會進位溢出，遮罩可以偷懶少 AND 幾次。 4. 驗證：與逐位迴圈版、__builtin_popcount 三方比對。

next_pow2 右移 OR 塗滿法：

觀察：2 的冪 = 「單一個 1」。若能把 x 變成「最高位 1 以下全是 1」（如 0001 0110 → 0001 1111），再 +1 就進位成單一個 1（0010 0000）。
塗滿的辦法：x |= x>>1 把最高位 1 複製到下一位（現在有 2 個連續 1）；x |= x>>2 把 2 個變 4 個；再 4、8、16—— 指數成長，5 步塗滿 32 位。
開頭的 x-- 是關鍵：讓「恰好是 2 的冪」的輸入不被推大一級（16 應回 16 不是 32）。x-1 讓 16 變 15，塗滿後 +1 回 16。
邊界：x <= 1 直接回 1（0 的話 x-- 會繞回 UINT_MAX 全塗滿， +1 溢位成 0，所以要特判）；x > 2³¹ 本來就無解（會溢位回 0），在註解註明即可。

參考解答

/*
 * ex5_popcount_pow2.c — 練習 5：無迴圈 popcount 與 next_pow2
 *
 * 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_popcount_pow2.c
 * 執行：/tmp/out
 *
 * 兩個經典的「無迴圈位元魔法」：
 *   popcount32(x)：分治法數 1 的個數（5 步定案）
 *   next_pow2(x) ：回傳 >= x 的最小 2 的冪（右移 OR 塗滿法）
 */
#include <stdio.h>
#include <stdint.h>

/*
 * 分治 popcount：
 *   第 1 步：每 2 位一組，組內相加（2 位最多存 2，夠）
 *   第 2 步：每 4 位一組相加（4 位最多存 4）
 *   之後 8、16、32 位一組……log2(32)=5 步完成。
 *
 * 遮罩（32 位）：
 *   0x55555555 = 0101...  隔 1 取 1
 *   0x33333333 = 0011...  隔 2 取 2
 *   0x0F0F0F0F = 00001111...
 *   0x00FF00FF、0x0000FFFF
 *
 * 第 1 步的 x - ((x>>1)&0x5555...) 是等價的省指令寫法：
 * 對每 2 位 (ab)：ab - a = 該組的 1 數（00->00,01->01,10->01,11->10）。
 */
static int popcount32(uint32_t x)
{
    x = x - ((x >> 1) & 0x55555555u);                   /* 2 位小計 */
    x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);   /* 4 位小計 */
    x = (x + (x >> 4)) & 0x0F0F0F0Fu;                   /* 8 位小計 */
    x = x + (x >> 8);                                   /* 16 位小計 */
    x = x + (x >> 16);                                  /* 32 位總計 */
    return (int)(x & 0x3Fu);            /* 最大 32，6 位就夠 */
}

/*
 * next_pow2：>= x 的最小 2 的冪。
 * 想法：先 x-1（讓「恰好是 2 的冪」的輸入不被推大一級），
 * 然後用連續右移 OR 把「最高 1 位以下」全部塗成 1：
 *   x |= x>>1;  最高位的 1 複製到下 1 位
 *   x |= x>>2;  已有的 2 個 1 複製到下 2 位
 *   ... 1,2,4,8,16 之後 32 位內全塗滿
 * 最後 +1 進位成單一個 1 -> 2 的冪。
 * 邊界：x=0 定義回 1；x > 2^31 會溢位（回 0），呼叫端自行注意。
 */
static uint32_t next_pow2(uint32_t x)
{
    if (x <= 1)
        return 1;

    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

/* 對照用的笨方法（迴圈逐位數），驗證魔法版正確 */
static int popcount_naive(uint32_t x)
{
    int n = 0;
    while (x != 0) {
        n += (int)(x & 1u);
        x >>= 1;
    }
    return n;
}

int main(void)
{
    printf("=== popcount32: divide and conquer, no loops ===\n\n");

    uint32_t tests[] = {
        0x00000000u, 0x00000001u, 0x000000FFu, 0xAAAAAAAAu,
        0xDEADBEEFu, 0xFFFFFFFFu,
    };
    for (size_t i = 0; i < sizeof tests / sizeof tests[0]; i++) {
        uint32_t x = tests[i];
        int fast = popcount32(x);
        int slow = popcount_naive(x);
        printf("  popcount(0x%08X) = %2d  (naive %2d, builtin %2d)  %s\n",
               x, fast, slow, __builtin_popcount(x),
               (fast == slow && fast == __builtin_popcount(x))
                   ? "ok" : "MISMATCH");
    }

    printf("\n=== next_pow2: smallest power of two >= x ===\n\n");

    uint32_t xs[] = { 0, 1, 2, 3, 5, 16, 17, 100, 4096, 100000u };
    for (size_t i = 0; i < sizeof xs / sizeof xs[0]; i++)
        printf("  next_pow2(%6u) = %7u\n", xs[i], next_pow2(xs[i]));

    /* 「恰好是 2 的冪」必須回自己：x-1 那一步的存在理由 */
    printf("\n  exact powers stay put: next_pow2(64) = %u\n",
           next_pow2(64));
    return 0;
}

程式碼講解

popcount 五行各自對應一個「組寬加倍」步驟；前三步嚴格遮罩、後兩步可放鬆（16 位組的小計最大 16，不會撞到相鄰組），最後 & 0x3F 收掉高位殘渣。
x - ((x>>1) & 0x5555…) 這行值得在紙上枚舉 00/01/10/11 四種 2 位組合驗證一次——它是《Hacker's Delight》開篇第一式。
next_pow2 的 if (x <= 1) return 1; 同時擋掉兩個邊界： x=0（否則 x-- 繞回全 1，+1 溢位成 0）與 x=1（2⁰=1 本身）。
生產程式直接用 __builtin_popcount（編譯成單一 POPCNT 指令）與 __builtin_clz 版的 next_pow2；手寫版的價值在理解與可攜。
易錯處：next_pow2 忘記開頭 x--，next_pow2(16) 會錯誤地回 32；popcount 遮罩少打一個 5 或 3（如 0x5555555 少一位），高位計數整個錯掉——遮罩常數務必數滿 8 個十六進位字。

範例輸出

=== popcount32: divide and conquer, no loops ===

  popcount(0x00000000) =  0  (naive  0, builtin  0)  ok
  popcount(0x00000001) =  1  (naive  1, builtin  1)  ok
  popcount(0x000000FF) =  8  (naive  8, builtin  8)  ok
  popcount(0xAAAAAAAA) = 16  (naive 16, builtin 16)  ok
  popcount(0xDEADBEEF) = 24  (naive 24, builtin 24)  ok
  popcount(0xFFFFFFFF) = 32  (naive 32, builtin 32)  ok

=== next_pow2: smallest power of two >= x ===

  next_pow2(     0) =       1
  next_pow2(     1) =       1
  next_pow2(     2) =       2
  next_pow2(     3) =       4
  next_pow2(     5) =       8
  next_pow2(    16) =      16
  next_pow2(    17) =      32
  next_pow2(   100) =     128
  next_pow2(  4096) =    4096
  next_pow2(100000) =  131072

  exact powers stay put: next_pow2(64) = 64

常見錯誤解法對照

錯誤寫法	症狀	正解
位元操作用有號 int	右移／溢位行為不可攜	一律 unsigned（全單元）
`~0` 不帶 u	有號 -1 左移是 UB 溫床	`~0u`（練習 2、3）
移位量等於位元寬度	未定義行為，值隨平台亂跳	先取模＋n==0 特判（練習 3）
setbits 忘記 `y & mask`	y 高位污染其他欄位	先遮罩再平移（練習 2）
解包 565 低位補 0	純白變 (248,252,248)	位元複製（練習 4）
next_pow2 忘記 `x--`	2 的冪被推大一級	先減一再塗滿（練習 5）

練習題與詳解 — 位元運算技巧

練習 1：print_binary（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 2：setbits（K&R 2-6）（難度：基礎）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 3：invert 與 rightrot（K&R 2-7、2-8）（難度：進階）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 4：RGB565 顏色打包／解包（難度：進階）

題目

解題思路

參考解答

程式碼講解

範例輸出

練習 5：無迴圈 popcount 與 next_pow2（難度：挑戰）

題目

解題思路

參考解答

程式碼講解

範例輸出

常見錯誤解法對照

Related articles

練習題與詳解 — 單元 01：C 語言入門（Getting Started）

單元 01：C 語言入門（Getting Started）

練習題與詳解 — 單元 02：變數與基本型別（Variables & Types）

單元 02：變數與基本型別（Variables & Types）

練習題與詳解 — 單元 03：運算子與運算式（Operators & Expressions）

單元 03：運算子與運算式（Operators & Expressions）

Related articles

C Programming Language 中文 Updated 2026-08-02

練習題與詳解 — 單元 01：C 語言入門（Getting Started）

本檔提供本單元練習題的完整詳解。強烈建議先自己動手做：每題先只看「題目」段落，自己寫完、編譯、執行之後，再回來對照「解題思路」與「參考解答」。所有解答的完整程式碼也放在 exercises/ 資料夾中，可直接編譯：
Read article →

C Programming Language 中文 Updated 2026-08-01

單元 01：C 語言入門（Getting Started）

C 語言由 Dennis Ritchie 於 1972 年前後在貝爾實驗室（Bell Labs）開發，最初的目的是重寫 UNIX 作業系統。它的前身是 Ken Thompson 的 B 語言，而 B 又源自 BCPL。1978 年 Kernighan 與 Ritchie 出版了第一版《The C Programming Language》（俗稱 K&R），1988 年的第二版對應 ANSI C（C89）標準，也就是本教程的主軸。
Read article →

C Programming Language 中文 Updated 2026-08-02

練習題與詳解 — 單元 02：變數與基本型別（Variables & Types）

本檔提供本單元練習題的完整詳解。先自己動手做：每題先只看「題目」，寫完、編譯、執行後再對照「解題思路」與「參考解答」。完整程式碼都在 exercises/ 資料夾，可直接編譯：
Read article →

C Programming Language 中文 Updated 2026-08-01

單元 02：變數與基本型別（Variables & Types）

變數是「有名字的記憶體位置」。使用前必須先宣告，讓編譯器知道它的名字與型別：
Read article →

C Programming Language 中文 Updated 2026-08-02

練習題與詳解 — 單元 03：運算子與運算式（Operators & Expressions）

本檔提供本單元練習題的完整詳解。先自己動手做：每題先只看「題目」，寫完、編譯、執行後再對照「解題思路」與「參考解答」。完整程式碼都在 exercises/ 資料夾，可直接編譯：
Read article →

C Programming Language 中文 Updated 2026-08-01

單元 03：運算子與運算式（Operators & Expressions）

重點：: 整數除法向零截斷：7 / 2 == 3、-7 / 2 == -3（C99 起明確定義）。 % 的結果符號跟隨被除數：-7 % 2 == -1。 % 不能用在浮點數；浮點取餘要用 <math.h> 的 fmod。
Read article →