互聯網校驗和位移

這幾乎肯定是一個非常愚蠢的問題，但由於某種原因，我在互聯網校驗和計算中遇到了麻煩。所有的算法基本上是這個樣子：互聯網校驗和位移

WORD chksm(WORD *startpos, WORD checklen){ 
ulong sum = 0; 
WORD answer = 0; 

while (checklen > 1) 
{ 
    sum += *startpos++; 
    checklen -= 2; 
} 

if (checklen == 1) 
{ 
    *(BYTE *)(&answer) = *(BYTE *)startpos; 
    sum += answer; 
} 

sum = (sum >> 16) + (sum & 0xffff); 
sum += (sum >> 16); 
answer = ~sum; 

return answer;}

我的一切除了線清晰：

sum += (sum >> 16);

它看起來像之前它增加了前16位的行底部16位，在頂部16位保留全零。如果是這樣，那麼現在不會總和>> 16現在等於零？如果是這樣，爲什麼那條線呢？

或者我（有可能）今天剛剛完全失智嗎？

來源

2009-10-20 Rob Lachlan

太棒了。感謝大家。 – 2009-10-20 22:20:16

你幾乎是正確的。

由於進位，高16位可能是1。例如，FFFF + FFFF => 1FFFE，或者FFFF + 1 => 10000。

來源

2009-10-20 22:13:13 DigitalRoss

我認爲一個ULONG爲32個比特寬，這意味着：

sum = (sum >> 16) + (sum & 0xffff) 
sum += (sum >> 16);

添加頂端sicteen比特和底部sisteen位在一起。然後下一行將前16位的結果相加;由於進位操作，其中可能有一個。

來源

2009-10-20 22:14:18

這是一個補碼和定義的一部分。您可以獲取任何溢出位並將它們添加回較低的16位。將它們加回來可能會導致進一步的溢出，所以你重複這個操作直到高位全部爲零。因此，在概念上它是這樣的：

while (sum >> 16 != 0) { 
    sum = (sum >> 16) + (sum & 0xffff); 
}

然而這個循環將只執行最多兩次，所以外在的循環是沒有必要的。第一次加法後，可能會或可能不會發生溢出，並且進位位以高16位結束。在這種情況下，高16位將爲0x0001，並且您將不得不再次添加該位進位。

想象一下在最初的while循環之後總和結尾爲0xffffffff的最壞情況。然後添加將按如下步驟進行：

sum = (0xffffffff >> 16) + (0xffffffff & 0xffff) 
    = 0xffff + 0xffff 
    = 0x1fffe 

sum = (0x1fffe >> 16) + (0x1fffe & 0xffff) 
    = 0x1 + 0xfffe 
    = 0xffff

而且有兩個補充，我們完成了高16位現在清除。這是最糟糕的情況，因此循環可以展開爲兩個補充。

（和然後畢竟你拿了最後一筆的補充，導致一個高度混淆的名字：這是補碼總和的補碼，花了我很長時間來包裹我的頭圍繞這個，我第一次實現它—特別是一個補數和不涉及~補碼操作符。）

來源

2009-10-20 22:17:40

互聯網校驗和位移

回答

相關問題