3

誰でもこれを説明できますか ((~(preRtcInseconds <<1)+1)>>1)

unsigned long preInseconds;
unsigned long curInSeconds;
unsigned long elapsedInSeconds;

if(curInSeconds>=preInseconds)
{
   elapsedInSeconds = curInSeconds - preInseconds;//does easy thing. no needs roll over
}
else{ //rollover
  preInseconds = ((~(preInseconds <<1)+1)>>1);
  elapsedInSeconds = curInSeconds + preInseconds;
}
4

3 に答える 3

4

の幅を。としunsigned longますw。unsigned longその場合、保持できる最大値は次のようになります。

ULONG_MAX = 2^w - 1

しましょうpreInseconds = a + b、ここで

a = preInseconds & (1ul << (w-1))
b = preInseconds & ((1ul << (w-1)) - 1)

a2^(w-1)であるかどうかに応じて、0またはのいずれかになりpreInseconds >= 2^(w-1)ます。次に、最初の左シフトが消滅しますa。

preInseconds << 1

与えるb << 1か2*b。

次に、ビット単位の補数が取得されます。

~(b << 1)

与えるULONG_MAX - (b << 1)。

の場合b == 0、1を加算するULONG_MAX - (b << 1)と0になり、それ以外の場合は0になります。

~(b << 1) + 1

与える

2^w - (b << 1)

次に、1ビットを右にシフトするb == 0と、0が生成されます。

2^(w-1) - b

そうでなければ。したがって、

preInseconds = ((~(preInseconds <<1)+1)>>1);

に設定preInsecondsします

2^(w-1) - b

の場合b != 0は0、。の場合は0になりますb == 0。

ついに、

elapsedInSeconds = curInSeconds + preInseconds;

したがって、 if was [分岐が行われた場合、、、したがって0ではない]elapsedInSecondsの値に設定され、curInSecondspreInseconds2^(w-1)elsepreInseconds > curInSeconds

curInSeconds - (preInseconds & (ULONG_MAX >> 1)) + 2^(w-1)

そうでなければ。

その操作の目的がわかりません。の場合preInseconds > curInSeconds、計算

curInSeconds - preInseconds

結果として

(2^w - preInseconds) + curInSeconds

これは（数学的に）と同じです

(2^w + curInSeconds) - preInseconds

これは、カウンターが最後に取得されてから1回curInSecondsロールオーバーした場合の経過時間です。これは、現在のカウンター値が前回よりも小さい場合に発生したと考えられます。それは理にかなっています。preInseconds

elseブランチで行われた体操で、

  • が、になる場合preInseconds <= 2^(w-1)、ロールオーバーされた現在のカウンターと前のカウンターの差からマイナスelapsedInSecondscurInSeconds - preInseconds + 2^(w-1)2^(w-1)
  • の場合preInseconds > 2^(w-1)、x - 2^(w-1) == x + 2^(w-1)符号なし算術では、と同じ結果が得られcurInSeconds - preInSecondsます。

したがって、curInSecondsロールオーバーが1回と仮定すると、ロールオーバーが前の2^(w-1)イベントから2秒以上経過した場合を除き、前のイベントと現在のイベントの間の経過秒数が計算されます。ロールオーバーが発生した場合2^(w-1)は、実際の経過時間から秒が差し​​引かれます。

于 2012-12-19T20:37:10.250 に答える
2

これは、C の符号なし算術が mod 2^n であることを理解していない (または mod 2^n 算術を理解していない) 誰かによって書かれたバグのあるロールオーバー コードのように見えます。

elapsedInSeconds = curInSeconds - preInseconds;
if (curInSeconds < UNLONG_MAX/2 && preInseconds < ULONG_MAX/2)
    elapsedInSeconds &= ULONG_MAX/2;

つまり、mod 2^n 減算を行いますが、いくつかのケース (おそらくどのテスト ケースでもヒットしなかった) では、トップ ビットが間違っています (セットではなくクリア)。

これが意図的である可能性は漠然とあります。ここで行われているのは、両方の数値が <2^n-1 の場合は mod 2^n-1 の減算を行い、いずれかの数値が >= の場合は mod 2^n の減算を行うためです。 2^n-1 (nは unsigned long のビット単位のサイズ)。トップビットを常にクリアしている、またはクリアしていない可能性のあるハードウェアデバイスから時間が来ている場合、これは理にかなっている可能性があります。

于 2012-12-19T22:51:35.350 に答える
1

まず第一に、以下の私の議論はすべて、unsigned long型が 32 ビット幅であることを前提としています。そうでない場合は問題ありません。どれだけ広いかは問題ではありませんが、私の例ではすべて 32 ビット幅であると想定しています。そして、私は単にそれを示すために使用します.それは実際には のような標準型ではないuint32ことを知っているので,気にしないでください.uint32uint32_t

Daniel Fischer は、それぞれの低レベル操作を詳細に説明する素晴らしい仕事をしてくれました。ここでは繰り返しません。しかし、あなたが興味を持っているのは、低レベルの操作のそれぞれの意味ではなく、グループとして適用されるすべての操作の必要性だと思います。以下で説明しますが、とにかく必要ありません。実際、それらはわずかに間違っていますが、「現在の」カウンターの読み取り値が「前の」読み取り値に円の半分以上戻っている場合のみです。

実装の数学の背後にある「意味」に到達する前に、最初に、可能な限り最小のロールオーバーの場合に、elapsedInSeconds を計算する方法の簡単な例を見てみましょう。

preInseconds = 0xffffffff で、curInSeconds = 0x00000000 の場合、elapsedInSeconds は 1 になります。

preInseconds = preInseconds<<1;     // 0xfffffffe
preInseconds = ~preInseconds;       // 0x00000001
preInseconds = preInseconds+1       // 0x00000002
preInseconds = preInseconds>>1;     // 0x00000001
elapsedInSeconds = curInSeconds + preInseconds;
             ... =  0x00000000  +  0x00000001    = 1

...これはまさに私たちが期待するものです。偉大な。

ただし、興味深いことに、ロールオーバー処理ロジックは必要ありません。まったく。誰かが「現在」と「前」のカウンター値の差を計算しようとしているのを見るたびに、ロールオーバーのケースを処理するためにフープを飛び越えているのをいつも目にしますが、多くの場合、彼らは間違っています。状況の恥は、特別なケースでロールオーバーを処理することは決してないということです2 の累乗サイズのカウンターに必要です。カウンターのフル スケール (ロールオーバーするポイント) がデータ型のサイズよりも小さい場合は、結果をカウンターのビット数にマスクする必要がありますが、実際にロールオーバーを処理するのはこれだけです。その場合は、ロールオーバーしたかどうかを気にせずに毎回マスキングを行うだけです (これにより、分岐命令も回避されるため、高速になります)。ロールオーバー ポイントは uint32 のフルスケール値であるため、結果をマスクする必要さえありません。

理由は次のとおりです。

上記のように、preInseconds=0xffffffff および curInSeconds=0 と仮定します。繰り返しますが、結果は 1 になるはずです。ロールオーバーを気にしない場合は、結果として curInSeconds-preInseconds を取得します。ただし、ロールオーバーの場合、減算操作によってアンダーフローが発生します。どういう意味ですか？これは、処理しているビット数が多い場合 (つまり、別の uint32 が 64 ビット複合カウンターの上位ワードとして使用されている場合)、上位ワードから 1 を借りる必要があることを意味します (ちょうど小学校のように) 10 進数での減算)。しかし、あなたの場合、借りるより高い言葉はありません。それで大丈夫です。本当。とにかく、あなたはそれらのビットを気にしません。探していた差の値が得られます。

elapsedInSeconds = curInSeconds - preInseconds;
             ... =  0x00000000  -  0xffffffff     = 1

...これにより、特別なロールオーバー処理ロジックがまったくなくても、期待される結果が得られます。

そのため、「確かに、あなたの些細な例ではうまくいきますが、ロールオーバーが巨大な場合はどうなるでしょうか?」と考えているかもしれません。よし、その可能性を探ってみよう。次に、preInseconds=0xffffffff および curInSeconds=0xfffffffe と仮定します。この例では、前のサンプルからほぼ完全にラップアラウンドしています。実際、あと 1 カウントしかありません。この場合、結果は 0xffffffff になるはずです (つまり、uint32 で表現できる値の数より 1 つ少ないカウント)。

elapsedInSeconds = curInSeconds - preInseconds;
             ... =  0xfffffffe  -  0xffffffff     = 0xffffffff

信じられない？これを試して：

#include <stdio.h>
typedef unsigned long uint32;
int main()
{
    uint32 prev = 0xffffffff;
    uint32 cur  = 0xfffffffe;
    uint32 result = cur - prev;
    printf("0x%08x - 0x%08x = 0x%08x\n", cur, prev, result);
}

それでは、実装の背後にある計算に戻りましょう。

その計算の「一種」は、preInseconds の 2 の補数を計算し、その結果を preInseconds に割り当てます。数値のコンピュータ表現と 2 の補数の加算と減算について少しでも知っていれば、差 AB を計算することは、A と B の 2 の補数の和、つまり A+(-B) を計算することと同じであることがわかります。これまでに調査したことがない場合は、Wikipedia または 2 の補数によってコンピューターの ALU が加算回路を減算に再利用できるようにする方法について調べてください。

あなたが示したコードで実際に「間違っている」のは次のとおりです。

数値の 2 の補数を計算するには、数値を反転し (0 ビットをすべて 1 に、1 ビットをすべて 0 に変更)、1 を加算します。それはとても簡単です。そして、それはあなたのコードが行っていることの「一種」ですが、完全ではありません。

preInseconds = preInseconds<<1;     // oops, here we lose the top bit
preInseconds = ~preInseconds;       // do the 2's complement inversion step*
preInseconds = preInseconds+1       // do the 2's complement addition step*
preInseconds = preInseconds>>1;     // shift back to where it ought to be,
                                    // but without that top bit we wish we kept

*NOTE: The +1 above only works here because the low bit is
 guaranteed to be 1 after the ~ operation, which carries a 1
 up into the 2nd bit, where it matters.

したがって、ここで本質的に数学が行っていることは、「ほぼ」2 の補数変換を実行することにより、preInseconds の値を手動で否定していることがわかります。残念ながら、プロセスの最上位ビットも失われています。これにより、ロールオーバー ロジックは、実際にはフル スケールの制限である 0xffffffff ではなく、eplapseInSeconds = 0x7ffffffff の最大値までしか機能しません。

これを次のように変換して、最上位ビットの損失をなくすことができます。

preInseconds = ~preInseconds;       // do the 2's complement inversion step
preInseconds = preInseconds+1       // do the 2's complement addition step

これで、2 の補数を直接計算したので、結果を計算できます。

elapsedInSeconds = curInSeconds + preInseconds; // (preInseconds is the 2's compl of its original value)

しかし、ばかげたことは、これが単にこれを行うことと計算上同等であることです...

elapsedInSeconds = curInSeconds - preInseconds; // (preInseconds is its unconverted original value)

そして、それを理解すると、コード例は次のようになります。

if(curInSeconds>=preInseconds)
{
    elapsedInSeconds = curInSeconds - preInseconds;
}
else // rollover
{
    elapsedInSeconds = curInSeconds - preInseconds;
}

...そもそもロールオーバーを特別なケースとして処理する必要がないことを明確にする必要があります。

于 2012-12-19T22:25:42.877 に答える