Java 소스 코드 Integer.bitCount 알고리즘 프로토타입 및 프로세스 분석(코드 포함)

알고리즘: 정수의 이진 표현에서 1인 비트 수를 계산합니다(해밍 가중치). 일반 알고리즘: 가장 낮은 비트부터 시작하여 하나씩 계산하는 알고리즘입니다. 1이든 상관없이 시간 복잡도는 O(n)이고, n은 총 비트 수입니다. 최적화 알고리즘: 이 알고리즘은 얼핏 혼란스러워 보이지만 잘 생각해보면 n-1 이후 n의 최하위 비트 1이 제거되고, n 비트와 AND 연산을 하면 n이 가장 낮은 비트가 된다는 원리를 찾을 수 있습니다. 비트 1이며 0으로 설정됩니다. 이후의 새 정수입니다.

Ordinary Algorithm

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 비트와 AND 연산되면 n은 가장 낮은 비트 1이 0으로 설정된 후 새로운 정수가 됩니다. 예: <p>rrreee</p> 다음과 같습니다. 이렇게 순환할 수 있으므로 많은 1, 시간 복잡도도 <code>O(n)이지만 n은 1인 비트 수를 나타내며 일반적으로 이전 것보다 좋습니다.

이미 최적의 알고리즘이라고 생각하면 그렇지 않습니다

Integer.bitCount

rrreee마지막으로 실제로 Java의 Integer 클래스는 이미 제공하고 있습니다. 비트를 계산하는 방법(부호 없는 오른쪽 시프트, 음수도 계산 가능) 얼핏 보면 WTF?원리: 인간의 뇌 앞에 1이라는 열이 놓여 있다고 상상해 보세요. 어떻게 계산할까요? ? Number by number, 첫 번째 알고리즘의 원리입니다. 아니면 2x2로 계산하나요? 이것이 이 방법이 구현되는 방식입니다. 아래 그림에 표시된 대로:

rrreee

각 두 비트는 그룹이며 각각 1의 수를 세고 결과를 다음 두 비트에 저장합니다. 예: 11 1이 2개 있고 결과는 10이며 10이 11을 대체하고 원래 위치에 저장됩니다. 그런 다음 덧셈 계산을 수행하고 모든 결과를 합산합니다. 덧셈 과정에서 2개씩 더해 계산 과정을 줄일 수 있습니다. 2비트는 1의 수를 계산합니다. 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1, 그래서 분명합니다.

알고리즘은 다음과 같이 구현됩니다:

• 먼저 정수 i가 왼쪽 숫자를 지웁니다. i & 0x55555555 를 입력한 다음 오프셋을 추가합니다. (i >>> 1) & 0x55555555는 왼쪽 비트를 오른쪽으로 이동한 다음 왼쪽 비트를 지워 두 비트의 1 개수를 계산할 수 있음을 의미합니다. 0b1011=>0b0001 + 0b0101 = 0b0110왼쪽 두 자리에 1이 하나, 오른쪽 두 자리에 1이 두 개 있습니다.

• 이때, 각 두 자리의 통계 결과는 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단계: 실제로 4비트를 고려하여 각 바이트에서 1의 수를 최대 8(0b1000)까지 계산합니다. 마침내 비트 AND 연산을 수행하여 비트를 제거하고 & 연산을 줄일 수 있습니다. : i = (i + (i >>> 4)) & 0x0f0f0f0f#🎜🎜##🎜🎜#
  • #🎜🎜#4단계 및 5단계: 위와 같은 이유 , 마지막 위치를 제거할 수 있습니다. 그러나 int는 최대 32(0b100000)개의 1을 가질 수 있으므로 이 두 단계에서 비트를 지울 필요가 없습니다. 마지막 단계는 불필요한 비트를 지우는 것입니다: i & 0x3f#🎜🎜 ##🎜🎜 ##🎜🎜##🎜🎜#깨달음: 대단한 단순성, 표면적으로는 복잡해 보이는 알고리즘이지만 구현 원리는 우리 두뇌의 단순한 사고 논리입니다#🎜🎜#rrreee#🎜🎜#관련 기사: #🎜🎜# #🎜 🎜##🎜🎜##🎜🎜#Java 참조 소스코드 분석 코드 상세 설명#🎜🎜##🎜🎜##🎜🎜##🎜🎜#java 소스 코드 분석 Arrays.asList 메소드 상세 설명#🎜 🎜##🎜🎜##🎜 🎜#관련 동영상: #🎜🎜##🎜🎜##🎜🎜#Java 주석 종합 분석#🎜🎜##🎜🎜#

위 내용은 Java 소스 코드 Integer.bitCount 알고리즘 프로토타입 및 프로세스 분석(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!