4

この記事を読ん でいるときに、特定の数値のビットを交換するために Xor を使用して個々のビットを交換しています。

* ビットの範囲をスワップする例として、b = 00101111 (2 進数で表現) があり、i = 1 (右から 2 番目のビット) から始まる n = 3 の連続するビットを 3 つの連続するビットでスワップするとします。 j = 5から始まります。結果は r = 11100011 (バイナリ) になります。*しかし、私はそれがどのように機能しているのか理解できませんでした.
与えられたコードは

unsigned int i, j; // positions of bit sequences to swap
unsigned int n;    // number of consecutive bits in each sequence
unsigned int b;    // bits to swap reside in b
unsigned int r;    // bit-swapped result goes here

unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) - 1); // XOR temporary
r = b ^ ((x << i) | (x << j));

このコードがどのように機能しているかを明確にしてください。

4

2 に答える 2

4

これを段階的に行いましょう: (b >> i) と (b >> j) は、スワップしたいビットを最初のビットに移動します。

((b >> i) ^ (b >> j)) 次に、それらを XOR します。

((1U << n) - 1) この式は単純に 1111...1 を n 回 (バイナリで) したものです。

したがって、合計 x は XOR の結果であり、他のすべてのビットは 0 です。

(x << i) および (x << j) は、ビットを正しい位置に戻します。

with ((x << i) | (x << j)) いずれかに設定されているすべてのビットが結果に設定されます。

そして b ^ ((x << i) | (x << j)) は、元の部分と両方の部分の XOR されたビットを XOR することを意味します。x ^ x ^ y = y であることに注意してください。両方の部分でオリジナルが xor に 2 回出現しますが、2 番目の部分は 1 回だけなので、ビット スワップが発生します。

于 2012-09-11T06:38:15.553 に答える
3

各操作によって影響を受けるビットを制限するためにシフトを使用しています (つまり、作業を完了するために他のビットをシャッフルし、重要なビットのみを操作します)。その一環として、これらのビットを xor で反転し、シフトして元に戻し、元のビットと x-or することで元のビットに戻します。…そしてそれは泥のように澄んでいるから…

例えば。

XX...XX001 ^ XX..XX111 = XX..XX110  (xor the 2 sequences together + trash bits)
XX..XX110 & 0...0111 = 110 (keep only those bits we care about)
00101111 ^ 11001100 = 11100011 (and magic!)
于 2012-09-11T06:33:02.253 に答える