因特网校验和中的位移位

Question

这几乎肯定是一个非常愚蠢的问题，但由于某些原因，我在互联网校验和计算方面遇到了麻烦。所有的算法基本上看起来像这样：

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的和不是等于0吗？如果是这样，为什么那条线在那里？

或者我(很可能)今天只是精神完全失败了？

Answer 1

你几乎是对的。

由于进位，高16位可能是1。

例如，FFFF + FFFF => 1FFFE或FFFF + 1 => 10000。

Answer 2

这是一个人的补码和定义的一部分。您可以获取任何溢出的位，并将它们添加回较低的16位。将它们添加回去可能会导致进一步的溢出，因此您需要重复此操作，直到高位结束为全零。所以，从概念上讲是这样的：

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

但是，此循环最多只能执行两次，因此不需要显式循环。在第一次加法之后，可能存在溢出，也可能没有溢出，其中进位比特结束于高16比特。在这种情况下，较高的16位将是0x0001，您将不得不做更多的加法来添加回进位。

想象一下最坏的情况，在初始的while循环之后，sum以0xffffffff结束。然后，添加将按如下方式进行：

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

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

有了两个加法，当高16位现在被清除时，我们就完成了。这是最坏的情况，因此循环可以展开为两次相加。

(然后，在所有这些之后，你取最后一个和的补码，导致这个高度混乱的名称:一个补码和的一个补码。当我第一次实现它的时候，我花了很长时间来理解这个问题--特别是一个人的补码和不涉及~补码运算符。)

Answer 3

我认为ulong是32位宽的，这意味着：

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

将顶部十六位和底部sisteen位相加在一起。然后下一行对前16位的结果求和；由于进位操作，其结果可能为1。