方法一:我们都知道,要取出一个整数的每一位,最简单的算法逻辑为 :模10;除10.
例如:假如要输出 1234 这个数的每一位;算法如下:
#include<stdio.h>
int main()
{
int num = 0;
printf("请输入:");
scanf("%d",&num);
while(num)//123
{
int k =0;
k = num % 10;
printf("%d ",k);
num = num /10;
}
return 0;
}
输出结果为
可以看出用 模10;除10 这种方法是可以取出一个整数的每一位的;虽然运行结果是倒叙输出的,我会在后期采用递归的算法正序输出,由于在这里这不是重点,就不在详细演示递归的方法了。
由上述过程我们可以得到一些启发:求一个二进制位中1的个数 ,我们可以采用 模2,除2来计算。算法如下:
#include<stdio.h>
int main()
{
int count = 0;
int num = 0;
scanf("%d",&num);
while(num)
{
if(num % 2 ==1)
{
count ++;
}
num = num/2;//取十进制位的每一位为 %10 /10 ;所以取二进制为的每一位为 %2 /2;
}
printf("%d",count);
return 0;
}
结果如下
通过以上结果,发现我们所写的代码似乎是没有问题的,但是如果输入一个负数,还会输出正确的结果吗?
结果如下:
通过结果,我们发现 -1中1的个数为0;显然是错误的,我们都知道-1中1的个数为32。所以上述的代码是有问题的。
代码改进如下:
int main()
{
int count = 0;
int unsigned num = 0;
scanf("%d",&num);
while(num)
{
if(num % 2 ==1)
{
count ++;
}
num = num/2;
}
printf("%d",count);
return 0;
}
结果如下:
改进方法:在第四行定义了一个无符号的整型
方法二
分析:我们都知道,数据在计算机中的存储方式都为二进制形式,一个整型的字节数为4(32位机器),即三十二个bite位。我们可以通过循环把一个数的三十二位取出来依次和1相与,如果结果为1;采用一个 count 变量加一。
算法如下:
#include<stdio.h>
int one_bite(unsigned int x )
{
int i = 0;
int count = 0;
for( i = 0; i < 32; i++)
{
if(((x>>i) & 1) == 1)
{
count ++;
}
}
return count;
}
int main()
{
unsigned int n = 0;
scanf("%d",&n);
printf("%d\n",one_bite(n));
return 0;
}
结果如下:
代码分析:虽然结果正确,但是这个代码是繁琐的,需要循环三十二次,才能得到最后结果,效率不高。因此采用方法三;可以使代码执行效率更高。
方法三
分析:假设一个数字为15;它的二进制位为:
15: 00000000 00000000 00000000 00001111
(15-1): 00000000 00000000 00000000 00001110
二者取与运算: 00000000 00000000 00000000 00001110 (14)
14在和(14-1)与运算结果:00000000 00000000 00000000 00001100 (12)
……
以此类推
最后8和(8-1)与运算结果为:00000000 00000000 00000000 00000000
从上述运算规律可以看出:每次取完后的num都会和(num-1)相与;将相与的值赋给num;直到num的值为0;结束算法。代码如下:
#include<stdio.h>
int main()
{
int num = 0;
int count = 0;
scanf("%d",&num);
while(num)
{
num = num & (num-1);
count ++;
}
printf("%d",count);
return 0;
}
结果如下:
代码分析:代码精简,而且效率高。为求这道题的最佳方法。