【c语言】多种方法:将十进制数转化成二进制数,计算其中1的个数

时间:2021-04-14 11:09:21

以下是我学到的三种方法,如果大家还有更好的方法,可以讨论交流。

首先,我们得知道十进制怎样转化成二进制,如下图。

【c语言】多种方法:将十进制数转化成二进制数,计算其中1的个数

得到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上浪费许多时间,效率就不高了。

所以,为了提高效率,我们引入下面这种方法:

【c语言】多种方法:将十进制数转化成二进制数,计算其中1的个数

“按位与”方法就是将最低位的1借位,得到的数值与原值相与,重复此过程,直至结果为0.

也就是说在这种方法中,只要数值中还存在1,就会重复这个过程。

代码如下:

while(data)
{
data = data & (data-1);
count++;
}