Java source code Integer.bitCount algorithm prototype and process analysis (with code)

Algorithm: Count the number of bits in the binary expression of the integer that are 1 (Hamming weight). Ordinary algorithm: This should be the first algorithm that comes to mind. Starting from the lowest bit, count whether is 1, the time complexity is O(n), and n is the total number of bits. Optimization algorithm: This algorithm seems confusing at first, but if you think about it carefully, you can find the principle: after n-1, the lowest bit 1 of n is eliminated, and then ANDed with n bits, n becomes the lowest bit 1 and is set to 0 The new integer after.

Ordinary algorithm

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

should be the first algorithm that comes to mind. Starting from the lowest bit, counting whether it is 1 one by one, the time complexity is O(n) , n is the total number of bits.

Optimization Algorithm

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

This algorithm seems confusing at first glance, but if you think about it carefully, you can find the principle: After n-1, the lowest bit of n is 1 Eliminated, and then ANDed with n bits, n becomes a new integer after the lowest bit 1 is set to 0, such as:

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

There will be as many 1s as many times as you can through this cycle, and the time complexity is also O (n), but this n represents the number of bits that are 1, which is generally better than the previous one.
When we think this is already the optimal algorithm, it is not the case

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;
}

Finally, in fact, Java's Integer class has provided a method to count bits Bit (unsigned right shift, negative numbers can be counted), at first glance, WTF?
Principle: Imagine that when a column of 1 is placed in front of our human brain, how will we count? Number by number, the principle of the first algorithm. Or counting two by two? This is how this method is implemented. As shown below:

             二进制                       十进制
 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的位数计算过程

Each two bits are a group, count the number of 1's respectively, and then store the result in these two bits, such as: 11There are 2 1's , the result is 10, 10 replaces 11 and is stored in the original location. Then perform addition calculations and add up all the results. During the addition process, you can add two by two to reduce the calculation process.

Two bits calculate the number of 1: 0b11: 0b01 0b01 = 0b10 = 2, 0b10: 0b01 0b00 = 0b01 = 1, so it’s clear.

The algorithm is implemented as follows:

• First, the left bit of integer i is erased: i & 0x55555555, and then the offset is added. (i >>> 1) & 0x55555555 means: move the left bit to the right, and then erase the left bit, so that the number of 1's in the two bits can be calculated: 0b1011=>0b0001 0b0101 = 0b0110There is one 1 in the left two digits and two 1s in the right two digits.

• At this time, the statistical results of each two digits are stored in i, which can be added in pairs and finally summed.

Process:

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

Algorithm prototype:

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;
}

Time complexity O(1), ok, very ok! But when writing an article, you need to polish it, let alone the algorithm, and then the optimized implementation is implemented in Integer.
Optimization:

• Step 1: Calculate the number of 1’s with two bits: 0b11: 0b01 0b01 = 0b10 = 2, 0b10: 0b00 0b01 = 0b01 = 1. The research found that: 2=0b11-0b1, 1=0b10-0b1, can be reduced once to calculate: i = i - ((i >>> 1 ) & 0x55555555)

• The second step: There is currently no good optimization method

• The third step: Actually calculate each The number of 1's in byte is up to 8 (0b1000), accounting for 4 bits. You can finally perform bitwise AND operation to eliminate bits, reducing one & operation: i = (i (i >> > 4)) & 0x0f0f0f0f

• Steps 4 and 5: For the same reason as above, you can eliminate the position at the end. However, since int has at most 32 (0b100000) 1s, there is no need to erase the bits in these two steps. The last step is to erase the unnecessary bits: i & 0x3f

Enlightenment: Great simplicity, a seemingly complex algorithm, but its implementation principle is the simple thinking logic of our brain

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

Related articles:

Detailed explanation Java Reference source code analysis code

java source code analysis Arrays.asList method detailed explanation

Related videos:

Comprehensive analysis of Java annotations

The above is the detailed content of Java source code Integer.bitCount algorithm prototype and process analysis (with code). For more information, please follow other related articles on the PHP Chinese website!