bit manipulation - Why by using n&(n-1) is not able to calculate number of 1's bits?

Question

I found a video on youtube that says by using n&(n-1) we can able to count number of 1's bits and it's much faster than - right shifting the bits by one and then checking the last bit . When I wrote the code using this method to calculate number of bits it's giving output as 9 instead of 3 - if we 01011 as parameter.

I debug the program and not able to find why it's happening so ?I am confused when in while loop condition , both A and A-1 is 512, it get out of loop even A&(A-1) = 1000000000 not 0 (zero).

If anyone knows what I am missing please let me know .

#include <iostream>
using namespace std;    
int bits(unsigned int A){
        int counter=0;
        unsigned int t;
        while (A&(A-1))
        {
            counter++;
             A--;
        }
        return counter;
    }
    int main()
    {
        unsigned int A=01011;
        int res=bits(A);
        cout<<"Result is "<<res<<"
";
        return 0;
    }

Thanking You

Yours Truly,

Rishabh Raghwendra

question from:https://stackoverflow.com/questions/66062771/why-by-using-nn-1-is-not-able-to-calculate-number-of-1s-bits

Answer 1

This is the Kerningham trick to calculate the number of bits without shifting. (Original author precedes Kerningham by a decade, but mr K popularised it).

n&(n-1) peels off the least significant one, meaning that one should write the result back to n.

while (n) {
   ++counter;
   n&=n-1;
}