How do I determine how many ones are in the binary of an integer

  • 2020-04-02 00:51:01
  • OfStack


//Determines how many 1's there are in the binary bits of an integer
void totalOne(int x)
{
 int count = 0;
 while(x)
 {
  x = x & ( x - 1 );
  count++; 
 }
 printf("count = %d/n", count);
}

Cycle: X is equal to x & (x - 1); Count++; Until x is equal to 0. The time complexity of this method is order m.
Here, the binary bits of x can be represented as
                  X = the an an - 1-2... A0.
In the order from low to high, without loss of generality, suppose that the ith bit of x is the first binary bit of 1, that is, ai=1. At this time are:
                  x             = the an an - 1-2... Ai + 1100... 0                           < 1 >
                (x - 1)   = the an an - 1-2... Ai + 1011... 1                           < 2 >
Obviously, from equations 1 and 2, it can be concluded that after the first x & (x-1) :
                  X = the an an - 1-2... Ai + 1000... 0
Then repeat until there is no 1 in the x bit
As you can see from the above, every time x & (x-1) is executed, the lowest possible value of 1 in the binary bit of x is changed to 0 and the number is added by 1.
For now, an integer has a maximum of 64 bits, and all three methods can be considered 0(1).

Related articles: