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

Question

I know this is the code. But I'm not able to understand what it does

 `public static int bitCount(long i){
         i = i - ((i  > > > 1) & 0x5555555555555555L);
         i = (i & 0x3333333333333333L) + ((i  > > > 2) & 0x3333333333333333L);
         i = (i + (i  > > > 4)) & 0x0f0f0f0f0f0f0f0fL;
         i = i + (i  > > > 8);
         i = i + (i  > > > 16);
         i = i + (i  > > > 32);
       return (int)i & 0x7f;
 }`

Answer 1

Let's take 255 as an example. The bits are combined as we go along. First we start with 255 as 0b1111.1111 (8 1's in binary)

The first line of code is:

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

This line is combing every pair of 1's. Since we have 8 1's, we expect to combine our pairs, and get back something like 2,2,2,2. Since it's binary we'd expect 10101010.

Let's look at i > > > 1. i was 0b1111.1111 and this is shifting down 1, so we get 0b0111.1111. We take the intersection, &, with 0b0101.0101 (this is from 5 being 101 in binary). Doing this keeps half of our bits, specifically all the ones that were initially at an even spot (the 2nd, 4th, 6th, 8th bits from our initial number).

We then subtract this from our initial value, which is a bit hacky. We are trying to add our top bits to our bottom bits, so we could just do that:

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

The term on the left would be the top bits, and the term on the right would be the bottom bits. But we know i = 2*(top bits) + 1*(bottom bits), because top bits are upshifted by 1 (which is the same as multiplying by 2). So by subtracting the top bits 1 time, we are getting the same result.

Okay, so now we are 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. The code is:

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

We are getting the top 2 numbers in each group of 4, and the bottom 2 numbers, and we are adding them. 0x3333 = 0b0011.0011.0011.0011 so we can see that taking the intersection, &, with 3's keeps the bottom 2 numbers in a group. We get the bottom two numbers first, and then we shift i over 2 spots to get the top 2 numbers. And then we add: 0010.0010 + 0010.0010 = 0100.0100. Exactly as expected.

Next we add the 2 groups of 4 together.

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

0x0f0f = 0b0000111100001111, so if we take the intersection with this, we are keeping every 4 numbers. We add i to itself downshifted 4, so we compute 0100.0100 + 0000.0100 = 0100.1000. 4 + 4 should give back 8, and 8 = 0b1000, but the top "4" still needs to be removed. The intersection with 0f0f0f0f does this.

So now we have 0b1000, which is 8. The rest of the steps add in even higher bits (like 2 groups of 8 together, than 2 groups of 16..) but since our number (255) was only 8 bits long, the higher bits were all 0s, so this won't affect our result.

Answer 2

Explanation :

This methods returns the bits your long would take as binary number : https://www.tutorialspoint.com/java/lang/long_bitcount.htm

• > > > is the logical shift : It shifts the value by the number n standing after it ; The first n bits are filled with zeros : Difference between >>> and >>

• &is the bitwise and : https://www.tutorialspoint.com/java/java_bitwise_operators_examples.htm

• 0x3333333333333333L is just a way to express some bits to compare to in hexadecimal. Converter : http://coderstoolbox.net/number/

How it works :

• For example, let's take i=10 decimal = 1010 binary
• First Line : i = i - ((i > > > 1) & 0x5555555555555555L);
  • 0x5555555555555555L hexadecimal = 101010101010101010101010101010101010101 binary
  • 1010 is shifted by one bit : 0101
  • 0101 is bitwise compared to 101010101010101010101010101010101010101 : {0 = 1} = 0 , {1 = 0} = 0 , {0 = 1} = 0 , {1 = 0} = 0 : 0000
  • 0000 binary=0 decimal
  • 10(i) is subtracted 0
• Second Line : i = (i & 0x3333333333333333L) + ((i > > > 2) & 0x3333333333333333L);
  • 0x3333333333333333L hexadecimal =11001100110011001100110011001100110011 binary
  • (i > > > 2) means i is shifted by two : i=10, binary : 1010 ; after shifting : 0010
  • i(1010) compared to 11001100110011001100110011001100110011 is 1001 = 9 decimal
  • 0010 compared is 0001, whats 1.
  • 9+1=10=i

I think thats enough example. Hope it helps.

Answer 3

The algorithm is:

To count the number of 1-bits in a 2^n-bit number (in this case n = 6, but you could write this algorithm for any machine number size), split it into two halves and, using shift operations, simultaneously count the number of 1-bits in the left half and the right half, storing the result in the rightmost (least significant) bits of each half. Then combine these results by shifting the left-side to the right-side and adding.

This is a recursive algorithm---you now apply the same to both sides. The clever bit that makes it fast is that you can use shift operations which perform the algorithm on both halves simultaneously. So the algorithm is O(log(N)) where N = 2^n is the number of bits in your machine number.

So the last lines of code are doing the "recombining" for each quarter, then each half, then the whole thing.