代码之家 › 专栏 › 技术社区 › Rob Lachlan

互联网校验和中的比特移位

checksum bit-manipulation c

Rob Lachlan · 技术社区 · 16 年前

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

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现在等于零吗?如果是这样,为什么会有这条线?

3 回复 | 直到 16 年前

DigitalRoss 16 年前

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

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

然而,此循环最多只能执行两次,因此不需要显式循环。在第一次加法之后,可能会也可能不会出现进位位位于高位16位的溢出。在这种情况下,高位16位将是 0x0001 你还需要再添加一个进位位。

0xffffffff 在初始while循环之后。然后,添加将按如下方式进行:

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

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

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

(还有然后毕竟,你取了最后一个和的补码,这导致了一个非常令人困惑的名字:补码和的补语。我第一次实现它时花了很长时间才理解这一点,特别是一个人的补码和不涉及 ~ 补充操作员。)

John Kugelman Michael Hodel 16 年前

你几乎是对的。

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

例如, FFFF + FFFF => 1FFFE ,或者也许 FFFF + 1 => 10000 .

Robert Massaioli 16 年前

我以为ulong是32位宽,这意味着:

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

将顶部的四位和底部的四位加在一起。然后下一行对前16位的结果求和;由于携带操作,其中可能有一个。