計算機補數編碼介紹
簡介
補數就是為了處理正負號而發明出來的，假設不用補數，會需要額外的電路來處理 sign bit。
並且在
在不同 Endian 下，Sign bit (MSB) 會在不同記憶體位置
| 特性 | Big Endian (大端序) | Little Endian (小端序) |
|---|---|---|
| Sign Bit 位置 (MSB) | 起始位址 (Offset 0) | 結束位址 (Offset Size-1) |
| 判斷正負號 | 檢查記憶體第一個 Byte | 檢查記憶體最後一個 Byte |
| 優點 | 可讀性高：記憶體傾印 (Hex Dump) 時，順序跟書寫一致。 | 類型轉換方便：將 32-bit 轉為 8-bit (截斷) 時，記憶體位址不變 (都在 Offset 0)。 |
| 判斷正負快：讀第一個 byte 即可知正負。 | 計算優勢：加法運算從 LSB 開始，與記憶體順序一致。 | |
| 常見架構 | IBM Mainframes, SPARC, Motorola 68k | x86, x64 (Intel/AMD), RISC-V |
| 網路協議 | 標準 (Network Byte Order)：TCP/IP 協議規定使用此順序。 | 較少用於網路傳輸標準，傳輸前通常需轉換。 |
一補數
請直接參考 解讀計算機編碼 文章了解個補數運作，這邊稍微講解。
一補數只要把 0 變成 1，1 變成 0 即可，但他在做加法的時候，人需要「循環進位」，因此電路設計有點麻煩，另外一個缺點是有兩個 0。
一補數用在早期 1960 的電腦跟網路通訊協定的檢驗碼上面。
我們可以看到 Linux 有自己的 csum_partial() 函式就是再做此一補數 Checksum 的操作。
__wsum csum_partial(const void *buff, int len, __wsum wsum)
{
// 1. 型別轉換：把傳入的 __wsum (核心用來標記檢查碼的型別) 轉成一般的 unsigned int
unsigned int sum = (__force unsigned int)wsum;
// 2. 呼叫苦力：do_csum 是真正去讀取記憶體並執行累加的函式
// 它會算出 buff 這塊記憶體的總和。
// (注意：do_csum 通常是針對不同 CPU 架構高度優化的組合語言版本)
unsigned int result = do_csum(buff, len);
/* add in old sum, and carry.. */
// 3. 把「之前的總和 (sum)」加到「這次算出來的結果 (result)」
result += sum;
// 4. 關鍵的 1 補數進位處理 (End-around carry)
// 如果加法結果變小了 (溢位 Wrap-around)，表示產生了進位
// 要把那個溢出的 1 加回來
if (sum > result)
result += 1;
// 5. 回傳結果，繼續保持為 32-bit 的 __wsum 格式 (尚未摺疊)
return (__force __wsum)result;
}在無號數 (Unsigned) 加法中，如果 A + B = C，且 C < A (結果比其中一個加數還小)，那麼肯定發生了溢位 (Wrap around)。
Linux Kernel 先用 csum_partial 算出一個很大的 32-bit 數字，最後再用 csum_fold 把它壓縮回 16-bit，32-bit 可以當作兩個 16-bit 再做加法。
csum_partial 是 fenrus75 對 csum_partial() 函式的優化。
他發現現代網路傳輸中，硬體網卡已經做掉了大部分工作，CPU 剩下的主要任務是計算 IPv6 Header (固定 40 bytes) 的檢查碼。既然長度固定是 40，所有的 while 迴圈判斷、剩餘長度判斷（有沒有剩 1 byte? 剩 2 bytes?）全部都可以刪掉。這減少了 CPU 的分支預測壓力。
舊的程式碼花了很多力氣去檢查「記憶體位址是不是偶數？是不是 4 的倍數？」。如果不是，就會用很慢的 byte-by-byte 方式先處理對齊。現代 CPU (x86-64) 對於「非對齊記憶體存取 (Unaligned Memory Access)」的處理能力已經非常強，直接硬讀通常比「先檢查再處理」還要快。讓非對齊的情況速度直接翻倍（從 19.2 cycles 降到 11.1 cycles）。
利用 CPU 的「亂序執行 (Out-of-Order Execution)」引擎，同時計算兩條算式，打破了原本的 Serial Dependency（依賴鏈），速度大幅提升。
// 兩路同時進行，互不依賴
sum_A = data[0] + data[2] + ...
sum_B = data[1] + data[3] + ...
// 最後再合體
total_sum = sum_A + sum_B最後 csum_partial 通常有一個輸入參數是 initial_sum。但在計算 IPv6 Header 時，初始值通常都是 0。
二補數
簡單說正數 + 複數會等於 0，而 8-bit 可以表示 -128 (11111111) ~ 127 (00000001) 的數字。
並且用二補數，電腦不用在意正負，只要實做加法就好了。只有在 8-bit -> 16-bit 類似變大的情況，我們才要在意符號。
- 無號數搬家 (Zero Extension)：前面補 0，適用於當你用 unsigned interger
- 有號數搬家 (Sign Extension)：用 Sign Extension (補符號位)，適用於你用 signed interger
比較
- 二補數 $X$ 和 $-X$ 加起來要等於 0 (0000)
- 一補數 $X$ 和 $\sim X$ (反轉) 加起來要等於 全 1 (1111)
所以二補數等於一補數 + 1
應用
二補數要注意 abs(-128) 是錯誤的，不會有 128，標準函式庫的 abs() 要注意。
二補數也能讓我們拓寫更優美的程式。
#include <stdio.h>
#include <stdint.h>
int32_t test(int32_t x) {
int mask = x >> 31;
printf("mask = %d, x + mask = %d\n", mask, x + mask);
return (x + mask) ^ mask;
}
int main(void) {
printf("abs(INT32_MIN) = %d\n", test(-2147483648));
return 0;
}- mask 是 -1 (全 1)
- x ^ -1 等於 反轉所有位元 (~x)
- ~x - (-1) 等於 ~x + 1
- 這正是 二補數定義下的負號 (-x)