How does Long.bitCount () find the number of bits set?

Let's take 255 as an example. Bits are combined as they go. We first start at 255 as 0b1111.1111

(8 1 in binary)

First line of code:

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

      

        
        
        
      

    

This line is combing each pair of 1. Since we have 8 1s, we expect to match our pairs and return something like 2,2,2,2. Since this is binary, we expect 10101010.

Let's take a look at i > > > 1

. I was 0b1111.1111

and this is shifted down by 1, so we get 0b0111.1111

. Take the intersection,, &

s 0b0101.0101

(this is from 5 to 101 in binary). Doing this stores half of our bits, specifically all those that were originally out of the blue (2nd, 4th, 6th, 8th bit from our starting number).

Then we'll subtract that from our initial value, which is a bit of a hack. We're trying to add our top bits to our bottom bits, so we could just do this:

((i > > > 1) & 0x5555) + (i & 0x5555)

      

        
        
        
      

    

The term on the left will be the top bit, and on the right side will be the bottom bits. But we know that i = 2 * (upper bits) + 1 * (lower bits) because the upper bits are flipped by 1 (which is the same as multiplying by 2). So, subtracting the top bits 1 time, we get the same result.

Okay, now we're ready for the second line of code. We currently have 0b1010.1010

for i, and we are ready to add each pair of 2. We expect to get 4.4 (4 bits used in each half), or 0100.0100

in binary. Code:

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

      

        
        
        
      

    

We get the top 2 numbers in each group of 4 and the bottom 2 numbers, and we add them. 0x3333 = 0b0011.0011.0011.0011

so that we can see that taking the intersection,, &

with 3 keeps the bottom 2 numbers in the group. First we get the bottom two numbers and then we change the i to 2 spots to get the top 2 numbers. Then he added 0010.0010 + 0010.0010 = 0100.0100

. Exactly as expected.

Then add 2 groups of 4.

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

      

        
        
        
      

    

0x0f0f = 0b0000111100001111

so if we take an intersection with this, we store every 4 numbers. We add I to ourselves with a downshift of 4, so we calculate 0100.0100 + 0000.0100 = 0100.1000

. 4 + 4 should return 8 and 8 = 0b1000

, but the top "4" still needs to be removed. The intersection with 0f0f0f0f

does it.

So now we have 0b1000

what is 8. The rest of the steps add even higher bits (for example, 2 groups of 8 together, not 2 groups of 16 ..), but since our number (255) was only 8 bits in length, the higher bits were 0, so this won't affect our result.