Java ソース コード Integer.bitCount アルゴリズム プロトタイプとプロセス分析 (コード付き)

アルゴリズム: 1 である整数の 2 進数表現のビット数を数えます (ハミング重み): これが最初に思い浮かぶアルゴリズムです。最下位ビットから始めて、1 であるかどうかを数えます。 1 、時間計算量は O(n)、n は総ビット数です。最適化アルゴリズム: このアルゴリズムは最初はわかりにくいように思えますが、注意深く考えると、n-1 の後、n の最下位ビット 1 が削除され、n ビットと AND 演算され、n が最下位ビットになるという原理がわかります。 1 で、0 に設定されます。その後の新しい整数。

普通のアルゴリズム

public int bitCount(int num) {
    int count = 0;
    do {
        if ((num & 1) == 1) {
            count++;
        }
        num>>=1;
    } while (num > 0);
    return count;
}

が最初に思い浮かぶアルゴリズムでしょう。最下位ビットから順番に1かどうかを数え、時間計算量はO(n)で、nは総ビット数。 O(n)，n为总bit数。

优化算法

public int countBit2(int num) {
    int count = 0;
    while (num > 0) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

这个算法乍看很懵逼，但是仔细琢磨一下也能发现原理：n-1后，n的最低位的1被消除了，然后与n位与，n变为最低位1置为0后的新整数，如：

0b101100  减一  0b101011 最低位的1消除，0b101100 & 0b101011 = 0b101000

如此循环多少次就有多少个1，时间复杂度也是O(n)，但是这个n表示bit位为1的个数，总体是要比上一个优一点的。
当我们以为这已经是最优的算法了，事实却并非如此

Integer.bitCount

public static int bitCount(int i) {
    // HD, Figure 5-2
    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;
}

最后,其实java的Integer类已经提供了一个方法来统计bit位（无符号右移，可以统计负数的），乍看之下，WTF?
原理：想象一下，当一列的1摆在我们人脑的面前，我们会怎么数？一个一个数，第一个的算法的原理。或者两个两个地数？本方法就是如此实现的。如下图：

             二进制                       十进制
 1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
  01     10     10     10     10       1 2  2  2  2
          \     /       \     /           \/    \/
  01       0100           0100         1   4    4
                \       /                   \  /
  01               1000                1      8
      \          /                       \   /
          1001                             9
          
              767的二进制中的1的位数计算过程

每两位bit为一组，分别统计有几个1，然后把结果存到这两个bit位上，如：11有2个1，结果为10，10替代11的存储到原位置。然后进行加法计算，把所有的结果加起来。加的过程中呢又可以两两相加，减少计算流程。

两个bit计算1的数量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1，这样就清楚了。

算法实现如下：

• 首先整数i抹除左一位：i & 0x55555555，然后错位相加。(i >>> 1) & 0x55555555表示：左位移到右边，再把左位抹除，这样就可以计算两个bit位上1的个数了：0b1011=>0b0001 + 0b0101 = 0b0110左两位有1个1，右两位有2个1。

• 这时i中存储了每两位的统计结果，可以进行两两相加，最后求和。

过程：

0x55555555  ‭0b01010101010101010101010101010101‬
0x33333333  ‭0b00110011001100110011001100110011‬
0x0f0f0f0f  ‭0b00001111000011110000111100001111‬
0x00ff00ff  0b00000000111111110000000011111111
0x0000ffff  ‭0b00000000000000001111111111111111‬
0x3f        ‭0b00111111‬

0b11 11 11 11 11    (i & 0x55555555) + ((i >>> 1) & 0x55555555)  = 0b0101010101‬ + 0b0101010101 = 0b1010101010
0b10 10 10 10 10    (i & 0x33333333) + ((i >>> 2) & 0x33333333) = 0b1000100010 + 0b00100010 = 0b1001000100
0b10 01 00 01 00    (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f) = 0b1000000100 + 0b0100 = 0b1000001000
0b10 00 00 10 00    (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff) = 0b1000 + 0b10 = 0b1010
0b00 00 00 10 10    (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff) = 0b1010 + 0 = 0b1010
dec           10

算法原型：

public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

时间复杂度O(1),可以，很ok了！但是写文章都要润色下的，别说算法了，然后优化过后的就是Integer中的实现了。
优化：

• 第一步：两个bit计算1的数量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1。研究发现：2=0b11-0b1，1=0b10-0b1,可以减少一次位于计算：i = i - ((i >>> 1) & 0x55555555)

• 第二步：暂时没有好的优化方法

• 第三步：实际是计算每个byte中的1的数量，最多8（0b1000）个，占4bit，可以最后进行位与运算消位，减少一次&运算：i = (i + (i >>> 4)) & 0x0f0f0f0f

• 第四,五步：同上理由，可以最后消位。但是由于int最多32（0b100000）个1，所以这两步可以不消位，最后一步把不需要的bit位抹除就可以了：i & 0x3f

  最適化アルゴリズム

7    0b111
i = 7 - ((7>>>1) & 0x55555555) = 6 = 0b110
i = (6 & 0x33333333) + ((6 >>> 2) & 0x33333333) = 2 + 1 = 3 = 0b11
i = (3 + (i >>> 4)) & 0x0f0f0f0f = 3 & 0x0f0f0f0f = 3 = 0b11
i = 3 + (3 >>> 8) = 3 = 0b11
i = 3 + (3 >>> 16) = 3 = 0b11
i = 3 & 0x3f = 3

このアルゴリズムは最初はわかりにくいように思えますが、よく考えてみると原理がわかります。n-1 の後、n のうち最も低い 1 が削除され、その後、 n ビットと組み合わせると、次のように、最下位ビット 1 が 0 に設定された後、n は新しい整数になります:

rrreee

循環する回数だけ 1 が存在し、時間計算量も になります。 O(n) ですが、この n は 1 のビット数を示し、通常は前のものよりも優れています。

これがすでに最適なアルゴリズムであると思うと、そうではありません


Integer.bitCount

rrreee最後に、実際、Java の Integer クラスは、ビットをカウントするメソッド (符号なし右シフト、負の数をカウントできる) を提供しました。 )、一見すると、何ということでしょう?原理: 1 の列が人間の脳の前に置かれたとき、私たちはどうやって数えるでしょうか?数値ごとに、最初のアルゴリズムの原理。それとも2つずつ数えますか？これがこのメソッドの実装方法です。以下の図に示すように:

rrreee

各 2 ビットは 1 つのグループであり、それぞれ 1 の数を数え、結果をこれらの 2 ビットに格納します。たとえば、11 には 2 の 1 があり、結果は 10 です。10 は 11 を置き換えて、元の場所に保存されます。次に、加算計算を実行し、すべての結果を合計します。加算処理では、2 つずつ加算して計算処理を軽減できます。 2 つのビットで 1 の数が計算されます: 0b11: 0b01 + 0b01 = 0b10 = 2、0b10: 0b01 + 0b00 = 0b01 = 1 なので、これは明らかです。

アルゴリズムは次のように実装されます:

• まず、整数 i の左の桁が消去されます: i & 0x55555555、次にオフセットが追加されます。 (i >>> 1) & 0x55555555 は、左のビットを右に移動してから左のビットを消去し、2 つのビット内の 1 の数を計算できるようにすることを意味します。 0b1011=>0b0001 + 0b0101 = 0b0110左の 2 桁に 1 が 1 つ、右 2 桁に 1 が 2 つあります。

• このとき、2 桁ごとの統計結果は i に格納され、ペアで加算して最終的に合計することができます。 🎜🎜🎜🎜プロセス: 🎜rrreee🎜アルゴリズムプロトタイプ: 🎜rrreee🎜時間計算量 O(1)、わかりました、素晴らしい!しかし、記事を書く際にはアルゴリズムはもちろんのこと、磨きをかける必要があり、その最適化されたものがIntegerでの実装になります。 🎜最適化: 🎜
  • 🎜ステップ 1: 2 ビットの 1 の数を計算します: 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1コード>。研究の結果、2=0b11-0b1、1=0b10-0b1 は、i = i - ((i > >&gt ; 1) & 0x55555555)🎜🎜
  • 🎜ステップ 2: 適切な最適化方法はまだありません🎜🎜
  • 🎜ステップ 3: 各バイトの 1 の数を実際に計算します。 8 (0b1000)、4 ビットを占有するため、最終的にビット単位の AND 演算を実行してビットを削除し、& 演算を 1 つ減らすことができます: i = (i + (i >>> 4) ) & 0x0f0f0f0f 🎜🎜
  • 🎜ステップ 4 と 5: 上記と同じ理由で、最後の位置を削除できます。ただし、int には最大 32 (0b100000) の 1 を含めることができるため、これら 2 つのステップでビットを消去する必要はありません。最後のステップは、不要なビットを消去することです: i & 0x3f🎜🎜🎜。 🎜Enlightenment: The Great Way 最も簡単に言うと複雑なアルゴリズムに見えますが、その実装原理は私たちの脳の単純な思考ロジックです🎜rrreee🎜関連記事:🎜🎜🎜🎜Javaリファレンスソースコード解析コードの詳細説明🎜🎜🎜🎜 Java ソースコード解析の詳しい解説 Arrays.asList メソッド🎜🎜 🎜関連動画: 🎜🎜🎜Java アノテーションの徹底解析🎜🎜

以上がJava ソース コード Integer.bitCount アルゴリズム プロトタイプとプロセス分析 (コード付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。