23

この質問は、整数時間計算量でビットカウントアルゴリズム（Brian Kernighan）を読んだ直後に続きます。問題のJavaコードは

int count_set_bits(int n) {
  int count = 0;
    while(n != 0) {
      n &= (n-1);
      count++;
    }
 }

n &= (n-1)ここで何が達成されているのか理解したいですか？私は、数が2の累乗であるかどうかを検出するための、別の気の利いたアルゴリズムで同様の種類の構造を見てきました。

if(n & (n-1) == 0) {
    System.out.println("The number is a power of 2");
}
4

2 に答える 2

37

デバッガーでコードをステップ実行すると役に立ちました。

から始めると

n = 1010101 & n-1=1010100 => 1010100
n = 1010100 & n-1=1010011 => 1010000
n = 1010000 & n-1=1001111 => 1000000
n = 1000000 & n-1=0111111 => 0000000

したがって、これは 4 回繰り返されます。各反復は、1 に設定された最下位ビットが消えるように値を減らします。

1 ずつ減らすと、最下位ビットが反転し、すべてのビットが最初のビットまで反転します。たとえば、1000....0000 -1 = 0111....1111 がある場合、反転するビット数に関係なく、そこで停止し、他のビットセットはそのまま残ります。あなたとこれでn最下位ビットが設定され、最下位ビットだけがなる場合0

于 2012-09-12T07:23:42.690 に答える