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 ビットをすべてゼロのままにする直前の行のように見えます。その場合、合計 >> 16 はゼロに等しくなりませんか? もしそうなら、なぜその行があるのですか？

それとも、私は（おそらく）今日、完全な精神障害を抱えているのでしょうか?

4

3 に答える 3

4

これは、1 の補数和の定義の一部です。オーバーフロー ビットを取得し、それらを下位 16 ビットに追加します。それらを元に戻すと、さらにオーバーフローが発生する可能性があるため、上位ビットがすべてゼロになるまでこれを繰り返します。したがって、概念的には次のとおりです。

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

ただし、このループは最大 2 回しか実行されないため、明示的なループは必要ありません。最初の加算の後、桁上げビットが上位 16 ビットで終了するオーバーフローが発生する場合と発生しない場合があります。その場合、上位 16 ビットになり0x0001、そのキャリー ビットを追加するためにもう 1 つ追加する必要があります。

0xffffffff最初の while ループの後に合計が終了するという最悪のケースを想像してみてください。その後、追加は次のように行われます。

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

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

そして、上位 16 ビットがクリアされたので、2 つの追加が完了しました。これは最悪のケースであるため、ループを 2 つの加算に展開できます。

(そして結局、あなたは最終和の 1 の補数を取るので、これを非常に紛らわしい名前にします: 1 の補数和の 1 の補数です。私が最初にこれを理解するのに長い時間がかかりました。特に、1 の補数和には~補数演算子が含まれていません。)

于 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);

上のsicteenビットと下のsisteenビットを一緒に追加します。そして次の行は、上位16ビットの結果を合計します。キャリー操作のために1つ含まれている可能性があります。

于 2009-10-20T22:14:18.787 に答える