(最全解法)输入一个整数,输出该数二进制表示中1的个数。
题目:请实现一个函数,输入一个整数,输出该整数二进制表示中1的个数。
例如:把9表示成二进制是1001,有2位是1.所以,如数该函数9,则输出2
- 解法一
容易造成死循环
思路:先判断该数的二进制表示中最右边是不是1,再把输入的这个整数向右移动一位,此时原来处于右边第二位的数被放在了最右边,在判断是不是1;循环往复,直到输入的数字变为0为止。
如何判断最右边位是不是1,我们把输入的整数与1采用按位与运算“&”,可知1的二进制只有最右边是1,按位与运算只有同为真时才为真也就是同为1时结果才为1。
如此,输入的整数与1按位与运算结果位1,则表示最右边为1,否则为0.
int count_one_bits(int val)
{
int count = 0;//计数
int i = 0;
for (i = 0; i < 32; i++)//一个整数占4个字节,内存中占32比特位
{
if ((val >> i) & 1 == 1)
count++;
}
return count;
}
- 解法二
常规解法,不会死循环
思路:避免死循环,不要移动输入的整数n。
可以先把n与1做按位与运算,判断最低为是不是1。把1向左移动1位变成2,在与n那位与运算,这样就可以判断n的次低位是不是1,循环往复知道到n最高位判断完,1变成0,同时最为循环停止的条件。
int count_one_bits3(int val)
{
int count = 0;
int i = 0;
//根据类型获取循环次数
for (i = 1; i != 0; i <<= 1)
{
//把第i位移到第一位,和1进行按位与&运算,获取二进制值
if ((val & i) != 0)
{
count++;
}
}
return count;
}
- 解法三
利用奇偶数判断
思路:奇数的最右边的一位绝对是1
int count_one_bits(int val)
{
int count = 0;
int i = 0;
for (i = 1; i <= 32; i++)
{
//根据奇偶数判断第一位是否为1
//奇数的第一位肯定为1
if (val % 2 == 1)
{
count++;
}
//相当于右移,依次把其它位挪到第一位,再去判断
val = val / 2;
}
return count;
}
- 解法四
新想法,效率最高有几个1就执行几次
思路:把一个整数减去1,在于原数字做按位与运算,会把原数二级制位中最右边的1变成0.那么一个整数二进制表示中有几个1,就可以进行几次这样的操作。
0111减去1变成0110,二者进行与运算变成0110,则把原数做右边的1变成0.循环往复直到全为0结束。
int count_one_bits4(int val)
{
int count = 0;
while (val)//到最后val变成0,退出循环
{
val = val&(val - 1);//把原数二进制位中做右边的1变为0
count++;
}
return count;
}
总代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
/*统计一个整数的二进制中有几个1?*/
int count_one_bits(int val)
{
int count = 0;
int i = 0;
for (i = 0; i < 32; i++)
{
if ((val >> i) & 1 == 1)
count++;
}
return count;
}
int count_one_bits2(int val)
{
int count = 0;
int i = 0;
for (i = 1; i <= 32; i++)
{
if (val % 2 == 1)
{
count++;
}
val = val / 2;
}
return count;
}
int count_one_bits3(int val)
{
int count = 0;
int i = 0;
//根据类型获取循环次数
for (i = 1; i != 0; i <<= 1)
{
//把第i位移到第一位,和1进行按位与&运算,获取二进制值
if ((val & 1) == 1)
{
count++;
}
val >>= 1;
}
return count;
}
int count_one_bits4(int val)
{
int count = 0;
while (val)
{
val = val&(val - 1);
count++;
}
return count;
}
int main()
{
int val=0;
int ret = 0;
scanf("%d", &val);
ret = count_one_bits(val);
//ret=count_one_bits2(val);
//ret=count_one_bits3(val);
//ret=count_one_bits4(val);
printf("%d\n",ret);
system("pause");
return 0;
}