4

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

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 位中留下全零。如果是这种情况，那么 sum >> 16 现在不会等于零吗？如果是这样，为什么那条线在那里？

还是我（很可能）今天完全精神失常？

4

3 回答 3

4

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

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

然而，这个循环最多只能执行两次，因此不需要显式循环。在第一次加法之后，可能有也可能没有溢出，进位位在高 16 位结束。在这种情况下，高 16 位将是0x0001，您将不得不再做一个加法来添加该进位位。

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

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

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

有了两个加法，我们就完成了，因为现在高 16 位已经清晰了。这是最坏的情况，因此循环可以展开为两个加法。

（然后毕竟你取了最后一个和的补码，这导致了这个非常令人困惑的名字：一个补码的补码。我第一次花了很长时间才弄清楚这个问题实现了它 - 特别是一个人的补码和不涉及~补码运算符。）

于 2009-10-20T22:17:40.113 回答
3

你几乎是对的。

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

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

于 2009-10-20T22:13:13.133 回答
1

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

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

将顶部 12 位和底部 12 位相加。然后下一行对前 16 位的结果求和；由于进位操作，其中可能有一个。

于 2009-10-20T22:14:18.787 回答