この質問は、整数時間計算におけるビットカウントアルゴリズム (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");
}
ベストアンサー1
デバッガーでコードをステップ実行すると役に立ちました。
まず
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