8

Javaがintのビットセットをカウントする方法を調べていました。
私は次のような単純なことを頭に入れていました（これは正しいと思います）： 

public static int bitCount(int number){  
        final int MASK = 0x1;  
        int count = 0;  

        for(int i = 0; i < 32; i++){  
            if(((number >>> i) & MASK) == MASK){  
                count++;  
            }  
        }  
        return count;  
    }

代わりに、何をしているのかまったくわからない方法を見つけました（私には魔法のように思えます）： 

 i = i - ((i >>> 1) & 0x55555555);  
 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);  
 i = (i + (i >>> 4)) & 0x0f0f0f0f;  
 i = i + (i >>> 8);  
 i = i + (i >>> 16);  
 return i & 0x3f;

誰かがこれが何をするのか、そしてなぜ私が最初に考えたような単純な関数が悪いのか/悪いのかを理解するのを助けることができますか?

4

2 に答える 2

7

もちろん

i = i - ((i >>> 1) & 0x55555555);

5のビットパターンは0101（4ビット）なので、マスクはビットパターンを0116回繰り返したものです。この行は、数値の2ビットペアごとにビット数をカウントします。2ビットのペアを検討する場合(i >>> 1) & 0x1、上位ビットを下位位置に取得します。現在、4つの可能な2ビットパターンがあります

00 ~> 00 - 00 = 00
01 ~> 01 - 00 = 01
10 ~> 10 - 01 = 01
11 ~> 11 - 01 = 10

そして、各2ビットペアには、元の位置にあったビット数が含まれるようになりました。

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

次に、各4ビットグループ（別名ニブル）に含まれていたビットをカウントします。ニブルをでマスクすることにより、ニブル0x3 = 0011(b)の下位2ビットにあったビット数を取得し、ニブル(i >>> 2) & 0x3の上位2ビットからカウントを取得します。これらのカウントが追加されました。各カウントは最大2であったため、合計は最大4であり、ニブルを残しません。

i = (i + (i >>> 4)) & 0x0f0f0f0f;

これで、各オクテットのビットがカウントされます。各ニブルには、その場所のオリジナルに設定されているビット数が含まれています。右に4ビットシフトすると、カウントが各場所の上位ニブルから下位ニブルに移動し、これらが追加されます。次に、カウントを低次のニブルから隣接するオクテットの高次のニブルに移動しました。これは、によってマスクされてい& 0x0f0f0f0fます。各オクテットには最大8ビットを設定できるため、カウントによってオクテットの下位ニブルが残ることはありません。

i = i + (i >>> 8);

次に、隣接するオクテットのペアのカウントを追加します。

i = i + (i >>> 16);

ここで、上位2オクテットと下位2オクテットのカウントの合計を加算します。

return i & 0x3f;

最後に、低次のオクテットを除くすべてのオクテットがマスクされます。これは、高次のオクテットにまだ中間カウントが含まれているためです。

単純な実装が悪いと見なされる理由は、パフォーマンスです。複雑なビットハックは、使用する操作が少なく、ブランチがないため、高速です。ただし、間違えるのははるかに簡単です。

int（またはlong）のセットビットをカウントするもう1つの優れた方法は次のとおりです。

public static int bitCount(int n) {
    int count = 0;
    while(n != 0) {
        ++count;
        n = n & (n-1);
    }
    return count;
}

これn = n & (n-1)は、最後のセットビットをクリアし、n他のすべてをそのままにしておくために機能します。のビットパターンがでn終わる場合

...100...0

のビットパターンn-1は

...011...1

最後の1ビットの前のビットnは同じです。Javaでは、整数のオーバーフローにはラップアラウンドセマンティクスがあるため、負の数でも機能することが保証されています。したがって、の場合n = Integer.MIN_VALUE、ビットパターンはビットパターンと同じ100...0にn - 1なりInteger.MAX_VALUEます011...1。

于 2012-06-03T22:30:56.960 に答える
3

コンピューターのintの値の範囲は有限であるため、coolメソッドのみが機能します。計算の前に必要なすべてのマスクを知る必要があるため、無限の範囲（BigIntegerなど）では簡単に機能しません（他のクールなビットアルゴリズムも同様です）。

いずれにせよ、あなたはそれがどのように機能するかを読むことができます：http: //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

この章の最後にあります。

于 2012-06-03T22:26:01.443 に答える