问题:
对于一个字节(8bit)的变量,求其二进制中1的个数,要求算法的执行效率尽可能的高。
例如把9表示成二进制是1001,有2位是1,因此如果输入9,1的个数为2。
解法一:
可以举一个8位二进制的例子。对于二进制操纵,我们除以一个2,原来数字就会减少一个0(向右移一位)。如果除的过程中有余,那么久表示当前位置有一个1。
以10100010为例:
第一次除以2时,商为1010001,余为0
第二次除以2时,商为101000,余为1
因此,考虑利用整形数据除法的特点,通过相除和判断余数的值进行分析。
-
intCount(inta)
-
{
-
intcount=0;
-
while(a)
-
{
-
if(a%2==1)
-
{
-
count++;
-
}
-
a=a/2;
-
}
-
returncount;
-
}
解法二:位操作
使用位操作同样达到相除的目的。
使用与操作(&)来判断最后一位是不是1,判断完后向右移一位,继续判断。
可以把这个八位数与00000001进行与操作,如果结果为1则表示这个八位数最后一位为1,否则为0。
-
intCount(inta)
-
{
-
intcount=0;
-
while(a)
-
{
-
count+=a&0x01;
-
a>>=1;
-
}
-
returncount;
-
}
位操作要比除法取余操作效率要高许多。
解法三:
作者用到一个巧妙的方法,自己与自己减1相与,(例:10100010 & 10100001 = 10100000)从而到达消去最后一位1,通过统计循环次数达到计算1的个数的目的,这个方法减少了一定的循环次数。
具体解析看看原著。
-
intCount(inta)
-
{
-
intcount=0;
-
while(a)
-
{
-
a=a&(a-1);
-
count++;
-
}
-
returncount;
-
}
解法四:分支操作
解法三的复杂度降到O(M). 其中M为1的个数。这效率已经足够高了。
如果还不满足,还有一种方法。既然才是一个8位的数据(0~255),可以直接0~255的情况罗列出来,使用分支操作,得到答案。
这个方法看似很直接,但是效率可能会比其他方法要低。具体情况具体分析。如果a = 0比较一次就会得到答案,但是a = 255比较255次才得到答案
-
intCount(inta)
-
{
-
intcount=0;
-
switch(a)
-
{
-
case0x0:
-
count=0;
-
break;
-
case0x1:
-
case0x2:
-
case0x4:
-
case0x8:
-
case0x10:
-
case0x20:
-
case0x40:
-
case0x80:
-
count=1;
-
break;
-
case0x3:
-
case0x6:
-
case0xc:
-
case0x18:
-
case0x30:
-
case0x60:
-
case0xc0:
-
count=2;
-
break;
-
-
}
-
returncount;
-
}
解法五:查表法
直接把0~255相应1的个数直接存在数组中,采取以空间换取时间。
-
intCountTable[256]=
-
{
-
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
-
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
-
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
-
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
-
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
-
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
-
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
-
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
-
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
-
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
-
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
-
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
-
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
-
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
-
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
-
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
-
};
-
-
intCount(inta)
-
{
-
returnCountTable[a];
-
}
分享到:
相关推荐
对于一个字节(8bit)的变量,求其二进制表示中“1”的个数,要求算法的执行效 率尽可能地高。
(android demo)算法实现:计算十进制数N的二进制形式中包含数字1的个数
求二进制数中1的个数
C++计算一个数字的二进制中0或1的个数原理及代码
d行对应每个测试数据,把转换成的2进制数中哪一位是1的位数输出,按升序排列。 (比如说1101,它的第3位是1,第2位是1,第1位是0,第0位是1,所以输出 0 2 3) 输入样例: 1 13 输出样例: 0 2 3
判断32位无符号整数二进制中1的个数,与大家分享下。不是原创
二进制中 1 的个数请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。示例 1:输入:000000000000000000000000000010
c语言编程题:从键盘输入一个十进制数,将其转换为二进制、八进制和十六进制数,并同时输出。
将ASCII码十进制数转换为二进制数,并显示出来。
汇编语言二进制数和十进制数相互转换课程设计!
将十进制数转化为7位二进制数的matlab M文件
统计整数的二进制表示形式中有几个1(java实现),代码中有三种方法,分别是利用除、余的方法,位运算,以及利用“与”运算的方法。其中第三种方法效率最高,二进制数中有几个1,算法中的循环内的运算就执行几次。
十进制转化成二进制数实现,c++描述。用c++描述十进制转化成二进制数实现,时间复杂度较低
二进制中1的个数.md
从键盘输入一个十进制数,二进制显示 从键盘输入一个十进制数,二进制显示
用c语言写的小程序,功能是将十进制数转换为二进制数。
实验二 数制转换 将一个十六位二进制数转换为十六进制数并在屏幕输出
汇编实现统计输入数据中1的个数,转换为二进制判断
这个是个c的小程序,适合初学者。内容是将一个八进制的数转换成二进制的数。
Delphi - 判断一个二进制数中有多少个1.mht