3

popcount（セットビットの数）を実行するための適切な方法を探しました。私はこれをここで見つけました

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for(c = 0; v; c++) 
{
    v &= v - 1; // clear the least significant bit set
}

いくつかの例を試してみると、それが機能するのは事実です。二項演算/表現のどのプロパティがそれを機能させますか？

ポップカウントとバイナリ表現に関するいくつかのさらなる読み方をほのめかしていただけますか？

4

2 に答える 2

4

v最初にnビットが設定されているイニシャルから始めています。

ゲームのポイントは、ループの各反復でカウントするビットを1つ少なくすることです。このようにして、最初のnの値を計算するために、n = 0のポイントに到達する前に必要だった、ループの反復回数を数えることができます。

n = 0の場合、v = 0であるため、ループはこの時点で停止することに注意してください。ただし、v> 0である限り、ループの本体を少なくとも1回実行します。各反復で、ビットセットが1つ少ないavになります。

これが理由です。必要な最初のプロパティはそれv && v == vです。これがビットのシーケンスです（正確なビット数はマシン/ OSによって異なりますv）。これは、最上位から最下位の順に並べ替えることができます。デクリメントするvと、次のことに注意できます。

  1. 最下位ビットはv[k]と呼ばれ、1に設定すると0に設定されます。
  2. をデクリメントしても、v[k]より重要なすべてのビットは変更されませんv。

したがって、vそのデクリメントとANDをとると、すべての最上位ビットが保持されますが、v [k]は0に設定されます。定義により、v [k]よりも重要でないすべてのビット、つまりv [k-1] ... v [0]は、v [k]が「1である最下位ビット」であるため、すでに0です。したがって、AND演算を行った後、重要度の低いすべてのビットは0のままになります。結果として、v && (v - 1)1に設定されたビットが1に1つ少なくなりますv。

于 2012-10-01T18:39:00.340 に答える
0

1ビットからビットを減算すると、0そのビットがaに変わり1、左側の次のビットから借用が発生し、1そこでも減算されます。これは、ビットに到達するまで左にカスケードし続けます。ここで、から1の減算はです。この時点で、減算は終了します。すべてを最初のセットビットまでに変換し、そのビットをからに変換しました。1100110

and前後の値を指定beforeすると、最初のビットの右側にafterゼロがあり、そのビットにゼロがあります。ゼロで結合されたものはすべてゼロであるため、すべてのゼロを元の値から保持し、単一ビットもゼロに設定します。

于 2012-10-01T19:26:54.133 に答える