1

この質問は、私の先生の古い最終試験の 1 つに現れました。答えに到達することを論理的に考えるにはどうすればよいでしょうか。

私は、ビット操作演算子と、16 進数と 2 進数の間の変換に精通しています。

int whatisthis(int x) {
  x = (0x55555555 & x) + (0x55555555 & (x >>> 1)); 
  x = (0x33333333 & x) + (0x33333333 & (x >>> 2));
  x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x >>> 4));
  x = (0x00ff00ff & x) + (0x00ff00ff & (x >>> 8));
  x = (0x0000ffff & x) + (0x0000ffff & (x >>> 16));
return x;
}
4

1 に答える 1

0

左シフトを忘れていませんか？

x = ((0x55555555 & x) <<< 1) + (0x55555555 & (x >>> 1));
x = ((0x33333333 & x) <<< 2) + (0x33333333 & (x >>> 2));
snip...

これは、左から右へのビットの反転になります。
ビットが 1 つずつではなく一緒に移動され、これにより O(log2(nbit)) のコストが発生することがわかります (
5 つのステートメントで 2^5=32 ビットを反転します)。

定数をバイナリで書き直して、それがどのように機能するかをよりよく理解するのに役立つ場合があります。

左シフトがない場合は、加算によってキャリーが発生し、明確な意味が見られないため、私はあなたを助けることができません...

編集：OK、興味深いので、これは1に設定されたビット数（人口カウントまたはポップカウントとも呼ばれます）をカウントするためのものです...これは、16ビットでのきしむSmalltalkクイックテストです

| f |
f := [:x |
    | y |
    y := (x bitAnd: 16r5555) + (x >> 1 bitAnd: 16r5555).
    y := (y bitAnd: 16r3333) + (y >> 2 bitAnd: 16r3333).
    y := (y bitAnd: 16r0F0F) + (y >> 4 bitAnd: 16r0F0F).
    y := (y bitAnd: 16r00FF) + (y >> 8 bitAnd: 16r00FF).
    y].
^(0 to: 16rFFFF) detect: [:i | i bitCount ~= (f value: i)] ifNone: [nil]

最初のステートメントは、各ビット ペアを処理します。ペアでビットが設定されていない場合は 00 を生成し、1 つのビットが設定されている場合は 01 を生成し、2 つのビットが設定されている場合は 10 を生成します。

00 -> 0+0 -> 00 = 0, no bit set
01 -> 1+0 -> 01 = 1, 1 bit set
10 -> 0+1 -> 01 = 1, 1 bit set
11 -> 1+1 -> 10 = 2, 2 bits set

したがって、各ペアのビット数をカウントします。

2 番目のステートメントは、隣接する 4 ビットのグループを処理します。

0000 -> 00+00 -> 0000 0+0=0 bits set
0001 -> 01+00 -> 0001 1+0=1 bits set
0010 -> 10+00 -> 0010 2+0=2 bits set
0100 -> 00+01 -> 0001 0+1=1 bits set
0101 -> 01+01 -> 0010 1+1=2 bits set
0110 -> 10+01 -> 0011 2+1=3 bits set
1000 -> 00+10 -> 0010 0+2=2 bits set
1001 -> 01+10 -> 0011 1+2=3 bits set
1010 -> 10+10 -> 0100 2+2=4 bits set

そのため、最初のステップでは各ビットのペアをこのペアに設定されたビット数で置き換えましたが、2 番目のステップではこのカウントをペアの各ペアに追加しました...

次に、8 つの隣接するビットの各グループを処理し、4 つの 2 つのグループのビット セットの数を合計します...

于 2012-12-07T19:13:53.997 に答える