Yesterday, when i was brushing the questions in LeetCode, i saw a code with little execution time in Submission, in which integer was used bitCount(i) method. i don't know what it does. After reading the notes, i know that this bitCount(i) method is to count several 1s in the binary corresponding to the integer i, but the writing method is confusing. Let's analyze it below.

Title Link: 1558. Get the minimum number of function calls of the target array

First, I searched several articles and read them. I gradually understood the general meaning and made records.

Reference blog: https://segmentfault.com/a/1190000015763941，https://blog.csdn.net/u011497638/article/details/77947324，https://blog.csdn.net/zhouzipeng000/article/details/56676885

Give you a number i, let you find how many 1s there are in the binary representation corresponding to i.

For example, let's start with a simple example, the number 7:. How many 1s are there in binary? It's easy. I can see three at a glance.

A more complicated one:, how many ones are there? I'm afraid I can't see it at a glance.

What we say here is that we scan from left to right with human eyes, check each bit, judge that this bit is 1, accumulate it once, and finally get the result.

That's not what the computer does. Take the number 7 as an example:.

For binary 0111, look at two bits at a time. When you see 01 for the first time, there is a 1 in it. We say it hasThe second time I see 11, there are two 1s in it. We say it hasOne, put it together, we say it hasOne.

Let's analyze how 01 and 11 become 01 and 10. Look at two at a time,，.

The purpose of this is to express the number of 1 in the original binary with binary value:There's a 1 in the. Use itexpress,There are two 1's in the, useexpress.

Start with the previous code, the prototype of bitCount():

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

hexadecimal	Binary
0x55555555	01010101010101010101010101010101
0x33333333	00110011001100110011001100110011
0x0f0f0f0f	00001111000011110000111100001111
0x3f	00000000000000000000000000111111

Just now, when we were doing & operation, we used, if you put 16Put it together, that's itFor the first line of the code, the binary is viewed two bits at a time, the number of 1 in each two bits is counted, and then placed in the original position.

If you can read the first and second digits of the original line, you can read the first and second digits of the original line.

......

The fifth line, look at the 32 bits of the binary each time, count the number of 1 in the 32 bits, and then put it in the original position.

At this point, the prototype of bitcount () can be understood. Let's look at the optimization part of 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;
}

takeTo analyze,Thus, the optimized writing method of the first line appears.

The second line remains unchanged.

In the third line, a combination law of & is made, which is equivalent to I = (I & 0x0f0f0f0f0f) + ((I > > > 4) & 0x0f0f0f0f);.

The fourth and fifth lines, because of an int, assume that its binary is all 1, that is, 32 1 at most. If there is a carry in the operation, ignore it first, and finally & a 0x3f, and remove the previous carry.

public static void main(String[] args) {
    int i = 144358622;
    System.out.println("i Decimal representation of:                         " + Integer.toBinaryString(i));
    i = i - ((i >>> 1) & 0x55555555);
    System.out.println("Look at 2 digits each time, count the number of 1 in 2 digits and put it in the original position:" + Integer.toBinaryString(i));
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    System.out.println("Look at 4 digits each time, count the number of 1 in 4 digits and put it in the original position:" + Integer.toBinaryString(i));
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    System.out.println("Look at 8 digits each time, count the number of 1 in 8 digits and put it in the original position:" + Integer.toBinaryString(i));
    i = i + (i >>> 8);
    System.out.println("Look at 16 bits each time, count the number of 1 in 16 bits and put it in the original position:" + Integer.toBinaryString(i));
    i = i + (i >>> 16);
    System.out.println("Look at 32 bits each time, count the number of 1 in 32 bits and put it in the original position:" + Integer.toBinaryString(i));
    i = i & 0x3f;
    System.out.println("Binary representation of the final result:" + Integer.toBinaryString(i));
}

Note that integer Tobinarystring() will ignore the leading 0. It needs to be added manually during analysis. Here is the data I simulated manually.

00-00-10-00-10-01-10-10-10-11-11-00-11-01-11-10((raw data)
00-00-01-00-01-01-01-01-01-10-10-00-10-01-10-01((Statistics per 2 digits)
0000--0001--0010--0010--0011--0010--0011--0011 ((Statistics per 4 digits)
00000001----00000100----00000101----00000110   ((Statistics per 8 digits)
0000000100000101--------0000100100001011       ((Statistics per 16 bits)
00000001000001010000101000010000               ((Statistics per 32 bits)