以下是我学到的三种方法,如果大家还有更好的方法,可以讨论交流。
首先,我们得知道十进制怎样转化成二进制,如下图。
得到10的二进制数为1010
那么我们会发现,10%2是判断二进制数的最后一位是0还是1,判断完成后向右移一位即10/2得到5,接着5%2判断二进制数的倒数第二位是0还是1,判断完成后向右移一位即5/2得2,重复这个过程,直到0/2结束。最终我们得到了10的二进制数1010.
根据上述思想,我们可以得到一个最初步的算法。
while(data>0)
{
if(data%2==1)
{ count++; }
data = data/2;
}
但是我们也可以再简便一些,方法如下:
while(data>0)
{
if(data & 0x1) //与最低位相与,判断是0还是1
{ count++; }
data = data>>1; //向右移1位
}
可是上述的两种方法通常适合二进制数的1比较集中出现在低位的情况,例如:101101
但是如果是1100000这样的数呢,它会在前面的0上浪费许多时间,效率就不高了。
所以,为了提高效率,我们引入下面这种方法:
“按位与”方法就是将最低位的1借位,得到的数值与原值相与,重复此过程,直至结果为0.
也就是说在这种方法中,只要数值中还存在1,就会重复这个过程。
代码如下:
while(data)
{
data = data & (data-1);
count++;
}