求一个整数的bit位中1的个数

fallening_cu

回复 5# 塑料袋

分治这种方法最好只在面试的时候用来 sm 考官，自己用的时候还是老老实实地地查表吧
   

safedead

回复 10# blackuhlan


   

这个。。。
我咋感觉你这是单片机上的程序呢？

sleepcat

http://www.myfavor.org/program/2011-10-03/359.html

一个无符号数，写一个函数将其2进制的位数为1的个数返回出来。
#include<stdio.h>
int main()
{
    int x=0xF1A0;
    int i=0;
    while(x)
    {
        x &= x-1;
        ++i;
    }
    printf("count=%d\n", i);
    return 0;
}
其实，最关键的部分就是“x &= x -1; ”
说明：不管二进制是什么，减1就会从右到左把0变为1，直至碰见1，把1变为0才结束.
如果x=x&(x-1), 就是把从左到右连续的0都变为1，并且遇到的第一个1变为0！
举例：10010100000  减1  就是：10010011111  ，再“&”就等于 10010000000  （红色部分）
这样循环一次，就是把最右边的1变为零。
有多少个1，就循环多少次。直到最后x的值变为0

seesunny

1、11楼说的对，直接查表法是最快的。可以参考<编程之美>
2、10楼的需要N多判断的case会转化为一堆的if语句。
3、3楼的算法需要更高的条件，要求知道，并且通过数学验证的，算法效率还远不及查表算法快。
4、要求是最快的。

captivated

回复 5# 塑料袋


    不错. 这段代码非常快, 效率高而且简洁. 很hack, 如你所讲, 这就是求unsigned int中bit位为1的个数的标准算法.(第一次发成unsigned long了. 对于64位构架上采用LP模型的编译器, unsigned long是64位, unsigned int还是32位. 嗯, 这种算法的唯一缺陷就是要求整数的位数固定, 稍微欠缺了点移植性.) 我大约是在一年前, 一个驱动工程师发上来这段代码求解释时才第一次见到这种做法. 什么查表法就是浮云.

starwing83

int hweight32(unsigned int w) {
    const char *p = "\0\1\1\2\1\2\2\3";
    int count = 0;
    while (w) {
        count += p[w&0x7];
        w >>= 3;
    }
    return count;
}

这样不是更简单么= =

塑料袋

starwing83 发表于 2012-07-07 21:19
int hweight32(unsigned int w) {
    const char *p = "\0\1\1\2\1\2\2\3";
    int count = 0;

32bit还看不出来什么

但我那个实际上是递归的办法，64bit上就要比循环查表NB了

starwing83

http://hi.baidu.com/sunyubo458/b ... 9b7a7f3812bb7a.html

找到一篇文章……

话说，64bit也就查个20多次的样子吧……如果用16位表（“\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4"）的话，也就查个16次啊……不过你得处理五遍，每次两个（或三个）位操作一个加法，一共是20次位操作加加法，也没快多少呗……

好吧……其实的确是那个比较牛逼，就是看到《C专家编程》里面的一句话（是这本书吧= =貌似不是这本），我也忘了哪儿说的了，说这个算法仅仅具有理论上的优势，其实查表更好一点（难道是《代码之美》么……）

最后，这么斤斤计较似乎有点过了，这年头编译器很牛逼的（参见那个gcc优化bswap的文，理论上我的方案比楼主的慢很多——位操作多得多，但实际上是一样的，因为编译器猜到了你要干嘛，直接优化成bswap了）。

cdtits

回复 18# starwing83


    谁评估一下两个程序的运行性能？不就更有说服力么？

刘五十三

最快就是直接用数字电路逻辑门，不可能还有比这更快的了。逻辑电路应该很简单。