C 語言位元運算精要：補數表示、經典技巧與實用函數庫

編輯：關於C語言

負數表示：二補數

現代電腦通用二補數表示有號整數，最高位為符號位。
十進位負數 → 二進位：加 1 → 取絕對值 → 轉二進位 → 求補。
二進位負數 → 十進位：求補 → 轉十進位 → 變號 → 減 1。
範例 -5 (8-bit)：-5 → -4 → 4 → 00000100 → 11111011。
32 位 int 範圍：-2^31 ~ 2^31-1；unsigned int：0 ~ 2^32-1。

基本位元運算

&（位元 AND）：遮罩清零。x & 0xF 保留低 4 位。
|（位元 OR）：設定位為 1。x | 0xF 置低 4 位為 1。

^（異或 XOR）：翻轉位、無暫存變數交換兩數。

void swap(int *a, int *b) {
    *a ^= *b; *b ^= *a; *a ^= *b;
}

~（位元 NOT）：逐位翻轉。0 ^ 0x7FFFFFFF 得最大正整數。
<< / >>：算術/邏輯位移（有號右移實作定義）。

實用位元操作函數庫

假設 unsigned int 為 32 位，提供通用工具函數：

1. 取得機器無號整數位寬

int int_size() {
    unsigned int bits = ~0;
    int size = 0;
    while (bits) { ++size; bits >>= 1; }
    return size;
}

2. 邏輯位移

unsigned int bit_shift(unsigned int value, int n) {
    int sz = int_size();
    if (n > 0 && n < sz) value <<= n;
    else if (n < 0 && n > -sz) value >>= -n;
    else value = 0;
    return value;
}

3. 循環位移（旋轉）

unsigned int bit_rotate(unsigned int value, int n) {
    int sz = int_size();
    if (n > 0) n %= sz; else n = -(-n % sz);
    if (n == 0) return value;
    if (n > 0) { // 左旋
        unsigned int bits = value >> (sz - n);
        return (value << n) | bits;
    } else {     // 右旋
        n = -n;
        unsigned int bits = value << (sz - n);
        return (value >> n) | bits;
    }
}

4. 取得第 p 位（從右起 0-based）

int bit_get(unsigned int value, int p) {
    int sz = int_size();
    if (p < 0 || p >= sz) return 0;
    return (value >> p) & 1;
}

5. 設定第 p 位為 1

unsigned int bit_set(unsigned int value, int p) {
    int sz = int_size();
    if (p < 0 || p >= sz) return 0;
    return value | (1u << p);
}

6. 擷取位欄位：從第 p 位向右 n 位

unsigned int bits_get(unsigned int value, int p, int n) {
    int sz = int_size();
    if (n < 0 || p < 0 || p + n > sz) return 0;
    return (value >> (p + 1 - n)) & ~(~0u << n);
}

關鍵：~(~0u << n) 產生低 n 位全 1 遮罩。

7. 設定位欄位：將 y 低 n 位寫入 value 第 p 位起 n 位

unsigned int bits_set(unsigned int value, int p, int n, unsigned int y) {
    int sz = int_size();
    if (n < 0 || p < 0 || p + n > sz) return 0;
    unsigned int mask = ~(~(~0u << n) << (p + 1 - n)); // 目標位清 0，其餘 1
    unsigned int src = bits_get(y, n-1, n);             // 取 y 低 n 位
    return (value & mask) | src;
}