Count number of Set bits in a long number [duplicate]

Question

I need to count number of set bits in a long number. Also I need to optimize the same. I'm using the following code:

public static int countSetBits(long number) {
    int count = 0;
    while (number > 0) {
        ++count;
        number &= number - 1;
    }
    return count;
}

Any modifications would be appreciated.

Answer 1

You can write it without subtraction as follow

public static int countSetBits(long number) {
    int count = 0;
    while (number > 0) {
        count += number&1L;
        number>>=1L;
    }
    return count;
}

If You want to use Java's built-in libraries then can use bitCount

Long.bitCount(number)

And if you want to see source code then

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