16位二進制數每4位求和：位運算經典面試題深度解析

題目描述

輸入一個十進制整數，程序自動轉為16位二進制表示，將其分為4組（每組4位），計算這4組數值的和。例如輸入305419896（十六進制0x12345678），二進制分組為0001 0010 0011 0100 0101 0110 0111 1000，每4位值分別為1,2,3,4,5,6,7,8，總和為36。

核心算法：掩碼與位移

char SumOfQuarters(unsigned short n) {
    int sum = 0;
    for (int i = 0; i < 4; ++i) {
        sum += n & 0xF;   // 掩碼提取低4位
        n >>= 4;          // 右移4位，準備下一組
    }
    return sum;
}

關鍵技術點解析

1. 掩碼提取：n & 0xF（即n & 15）利用二進制1111保留低4位，高位歸零
2. 算術右移：n >>= 4將次低4位移至低位位置，無符號數右移高位補0，符合邏輯右移語義
3. 循環4次：16位數恰好包含4組4位，固定迭代無需條件判斷
4. 返回類型：最大和為4 * 15 = 60，char（通常8位）足夠，但建議用int避免隱式轉換困惑

完整可運行程序

#include <stdio.h>
#include <stdint.h>  // 使用標準整數類型

uint8_t sum_nibbles(uint16_t n) {
    uint8_t sum = 0;
    for (int i = 0; i < 4; ++i) {
        sum += n & 0xF;
        n >>= 4;
    }
    return sum;
}

int main(void) {
    uint16_t input;
    printf("請輸入0-65535的整數: ");
    if (scanf("%hu", &input) != 1) return 1;
    
    printf("每4位之和: %hhu\n", sum_nibbles(input));
    return 0;
}

進階變體與優化

查表法（O(1)無循環）

static const uint8_t NIBBLE_SUM[16] = {
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
};

uint8_t sum_nibbles_lut(uint16_t n) {
    return NIBBLE_SUM[n & 0xF] 
         + NIBBLE_SUM[(n >> 4) & 0xF]
         + NIBBLE_SUM[(n >> 8) & 0xF]
         + NIBBLE_SUM[(n >> 12) & 0xF];
}

適合極端性能敏感場景（如嵌入式中斷服務程序），以256字節換取零分支預測失敗。

並行位運算（SWAR技術）

uint8_t sum_nibbles_swar(uint16_t n) {
    n = (n & 0x1111) + ((n >> 4) & 0x1111);  // 兩兩合併
    n = (n & 0x00FF) + ((n >> 8) & 0x00FF);  // 合併高低字節
    return n;  // 此時低8位即為結果
}

利用0x1111間隔掩碼實現SIMD式並行加法，無循環、無查表，適合無緩存嵌入式核心。

常見錯誤避坑指南

• 符號擴展陷阱：若用short而非unsigned short，右移可能算術補1導致錯誤
• 輸入範圍未驗證：scanf("%hu")配合uint16_t防止溢出
• 忽略大端序：本題按位運算與字節序無關，但涉及union或指針訪問時需注意

擴展思考

若擴展到32位整數每4位求和？只需將循環次數改為8，或查表法擴展至NIBBLE_SUM[256]按字節查表。若改為「每3位求和」？掩碼變為0x7，移位為3，但16位不被3整除，需處理邊界。

這道題考察位運算基本功、類型系統理解與工程化思維。掌握掩碼、移位、查表、SWAR四大技法，可應對絕大多數位級運算面試題。