C語言經典面試題：字符串反轉與統計字節中 1 的個數

題目一：字符串原地反轉

實現 void InvertStr(char *str)，將 "abc" 變為 "cba"。

核心思路：雙指針首尾交換

void InvertStr(char *str) {
    if (!str) return;
    char *left = str;
    char *right = str + strlen(str) - 1;
    while (left < right) {
        char tmp = *left;
        *left++ = *right;
        *right-- = tmp;
    }
}

關鍵點：

• 空指針檢查
• strlen 獲取長度，右指針指向最後有效字符（非 \0）
• left < right 條件避免重複交換中間字符
• 原地操作，O(1) 空間，O(n) 時間

題目二：統計一個字節中被置 1 的位數（Hamming Weight / Population Count）

輸入 unsigned char，返回二進制中 1 的個數。例：0b00000101 → 2。

方法一：逐位檢查 + 右移（8 次循環）

unsigned char countBits_v1(unsigned char x) {
    unsigned char cnt = 0;
    for (int i = 0; i < 8; ++i) {
        cnt += x & 1;   // 檢查最低位
        x >>= 1;        // 右移
    }
    return cnt;
}

方法二：Brian Kernighan 算法（n & (n-1) 消除最低位 1）

unsigned char countBits_v2(unsigned char x) {
    unsigned char cnt = 0;
    while (x) {
        x &= (x - 1); // 消除最低位的 1
        ++cnt;
    }
    return cnt; // 循環次數 = 1 的個數
}

平均循環次數少，面試加分項。

方法三：查表法（極致快，工程常用）

// 256 字節預計算表
unsigned char bitCountTable[256];

void initBitCountTable() {
    for (int i = 0; i < 256; ++i) {
        bitCountTable[i] = (i & 1) + bitCountTable[i >> 1];
    }
}

unsigned char countBits_v3(unsigned char x) {
    return bitCountTable[x];
}

方法四：並行加總（SWAR，無循環，32/64 位通用）

// 32 位版本
int popcount32(uint32_t x) {
    x -= (x >> 1) & 0x55555555;
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x += x >> 8;
    x += x >> 16;
    return x & 0x3F;
}

現代 CPU 有 POPCNT 指令，編譯器 -mpopcnt 可自動優化。

面試考察點總結

1. 指針運算熟練度：首尾指針、指針遞增遞減
2. 邊界條件：空指針、空字符串、單字符
3. 位運算技巧：n & (n-1)、查表、並行加總
4. 時間空間權衡：查表法空間換時間、SWAR 無分支
5. 硬件感知：提及 POPCNT 指令、SIMD 加速

總結

兩道看似基礎的題目，實則涵蓋指針、位運算、查表優化、硬件指令等核心功底。面試中寫出 v1 為及格，主動優化到 v2/v3 並說明場景適用性為優秀，能討論 CPU 指令集優化為專家級。