C語言位運算綜合實戰：指針、循環移位、拔河分組、鏈表排序

編輯：關於C語言

C語言位運算綜合實戰：指針、循環移位、拔河分組、鏈表排序

本文匯總多個位運算與指針相關的經典練習：字母大小寫轉換、大數加法、階乘位數、循環移位（左右）、拔河比賽分組優化、有序鏈表插入。展示位運算在實際問題中的強大表達力。

一、字母大小寫轉換（位運算精髓）


void to_upper(char *str, int n) {
    for (int i = 0; i < n; i++) {
        // 小寫字母第5位為1，大寫為0。差值32=0x20
        if (str[i] >= 'a') str[i] &= ~0x20;  // 或 str[i] -= 32;
    }
}
// 'a'=0x61, 'A'=0x41, 差異僅第5位(0x20)
// 大寫轉小寫：str[i] |= 0x20;

原理：ASCII 字母大小僅第 5 位不同。位運算無分支、極快。

二、大數加法（字符串模擬）


// 逆序存儲個位在前，逐位相加處理進位
// 核心邏輯：
// c[i] = (a[i] + b[i] + carry) % 10;
// carry = (a[i] + b[i] + carry) / 10;

突破類型範圍限制，任意長度整數運算基礎。

三、循環移位（右移/左移）


// 32位整數 n 右循環移 m 位
unsigned int ror(unsigned int n, int m) {
    m %= 32;
    return (n >> m) | (n << (32 - m));
}

// 左循環移
unsigned int rol(unsigned int n, int m) {
    m %= 32;
    return (n << m) | (n >> (32 - m));
}

// 關鍵：使用無符號類型，避免符號位擴展
// 移位量取模位寬，防止未定義行為

應用：加密算法、哈希函數、位圖旋轉、網絡字節序轉換。

四、拔河比賽分組（隨機搜索近似最優）

問題：n 人已知體重，分為兩隊各 n/2 人，使兩隊總重差最小。

NP難問題（分割問題），精確解需動態規劃 O(n*sum)。源碼採用蒙特卡洛隨機采樣：


int best_diff = INF;
for (int iter = 0; iter < 10000; iter++) {
    隨機選 n/2 人組成隊伍 A
    計算 diff = abs(sum_A - (total - sum_A))
    更新 best_diff
}

簡單實用，工程上常用近似算法（贪心+局部搜索、模擬退火、遺傳算法）。

五、有序鏈表插入（保持有序）


struct Node {
    int id;
    struct Node *next;
};

void insert_sorted(struct Node **head, struct Node *new_node) {
    struct Node **pp = head;  // 指向指針的指針
    while (*pp && (*pp)->id < new_node->id) {
        pp = &(*pp)->next;
    }
    new_node->next = *pp;
    *pp = new_node;
}
// 統一處理頭插/中間插/尾插，無需特殊判斷

技巧：pp 指向「存儲下一節點地址的指針變量」（即 head 或 prev->next），插入時直接修改 *pp，代碼極其簡潔。

六、位運算常用技巧總結

操作	代碼	應用
判斷奇偶	n & 1	替代 n%2
清除最低位1	n & (n-1)	計算1的個數、判斷2的冪
獲取最低位1	n & -n	樹狀數組、低位隔離
交換無臨時變量	a^=b; b^=a; a^=b;	寄存器級優化
絕對值(無分支)	(n^(n>>31))-(n>>31)	SIMD、GPU編程
向上取整除法	(a+b-1)/b	分頁、塊大小計算
判斷2的冪	n>0 && !(n&(n-1))	內存對齊、位圖

七、指針與位運算結合：硬件寄存器操作


// 設置 GPIO 寄存器第 3、5 位
#define SET_BITS(reg, mask) (*(volatile uint32_t*)(reg) |= (mask))
#define CLEAR_BITS(reg, mask) (*(volatile uint32_t*)(reg) &= ~(mask))

SET_BITS(GPIO_BASE + 0x04, (1<<3) | (1<<5));
CLEAR_BITS(GPIO_BASE + 0x04, (1<<2));

volatile 防止編譯器優化掉「看似無用」的寄存器讀寫，嵌入式開發必加。