首页 > 代码库 > 编程之美-02数字之魅-求二进制数中1的个数
编程之美-02数字之魅-求二进制数中1的个数
题目:求二进制数中 1 的个数
对于一个字节(8bit)的无符号整型变量,求其二进制表示中“1”的个数,要求算法的执行效率尽可能地高。
解法一:移位->判断->累计
解法二:除2->判断->累计
解法三:v &= (v -1)需要掌握
?
2345678int
num = 0;
while
(v)
{
v &= (v -1);
num++;
}
return
num;
?
2 | |
解法四:分支操作(swicth-case全部可能值),空间换时间。
?
2 | |
解法五:查表法(预定义结果表),空间换时间。
?
2 | |
解法六:二分法(32位)。
两两一组相加,之后四个四个一组相加,接着八个八个,最后就得到各位之和了。
?
2345678910int
Count(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return
x & 0x0000003F;
}
?
2 | |
解法七:HAKMEM算法。
三个一组,求出每组中1的个数,然后相邻两组归并,得到六个一组的1的个数,最后很巧妙的用除63取余得到了结果。
因为2^6 = 64,也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63),这里的等号表示同余。
这个程序只需要十条左右指令,而且不访存,速度很快。
?
23456789101112int
Count(unsigned x)
{
unsigned n;
n = (x >> 1) & 033333333333;
x = x - n;
n = (n >> 1) & 033333333333;
x = x - n;
x = (x + (x >> 3)) & 030707070707;
x = modu(x, 63);
return
x;
}
?
2
其他方法 http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。