Chinaunix

标题: 求一个整数的bit位中1的个数 [打印本页]
作者: ciedecem    时间: 2012-07-04 21:15
标题: 求一个整数的bit位中1的个数
给一个整数，求这个整数的bit位的1的个数，要求，最快算法:

int count(int ipNumber)
{
        int counter =0;
        int tmp(ipNumber);
        while( tmp != 0)
        {
                if ( tmp % 2 == 0)
                        tmp /=2;
                else
                {
                        ++counter;
                        tmp /=2;
                }
        }
        return counter;
}

我只想到了用将10进制转为2进制的方式，来求这个int数据中的bit位中1的个数。

可否使用移位运算，又该如何用？？还有没有其他方式？？

谢谢
作者: 塑料袋    时间: 2012-07-04 21:46
这个有标准的算法的

32位的int，做4次移位和加法运算，就能算出来。
作者: cdtits    时间: 2012-07-04 21:48
本帖最后由 cdtits 于 2012-07-05 09:48 编辑

这样行不？
  1. int count(unsigned int num)
  2. {
  3.     int n = 0;
  4.     while (num) {
  5.         if (num & 1)
  6.             n++;
  7.         num >>= 1;
  8.     }
  9.     return n;
  10. }
复制代码
作者: 塑料袋    时间: 2012-07-04 22:20
unsigned int hweight32(unsigned int w)
{
        unsigned int res = w - ((w >> 1) & 0x55555555);
        res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
        res = (res + (res >> 4)) & 0x0F0F0F0F;
        res = res + (res >> ;
        return (res + (res >> 16)) & 0x000000FF;
}
作者: 塑料袋    时间: 2012-07-04 22:21
本帖最后由 塑料袋 于 2012-07-04 23:07 编辑

  2. unsigned int hweight32(unsigned int w)
  3. {
  4.         unsigned int res = w - ((w >> 1) & 0x55555555);
  5.         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
  6.         res = (res + (res >> 4)) & 0x0F0F0F0F;
  7.         res = res + (res >> 8);
  8.         return (res + (res >> 16)) & 0x000000FF;
  9. }
复制代码
以前哥们有一次去novell面试，上来就问脑筋急转弯。
第一个疯狗咬人，人不能咬疯狗的，不会。
第二个就是这个，我该装装B，可是当时想也没想，直接说这种题早就有标准算法了。
然后over


@pmerofc，专家，评论下这段代码呗？
作者: noword2k    时间: 2012-07-05 09:26
http://graphics.stanford.edu/~seander/bithacks.html
作者: lxk899    时间: 2012-07-05 11:06
3#不错的。。。
作者: 塑料袋    时间: 2012-07-05 12:14
lxk899 发表于 2012-07-05 11:06
3#不错的。。。


我贴的那段代码才是王道啊，不信让@pmerofc来评论一下
作者: huxk    时间: 2012-07-05 13:10

上次貌似有谁发过一个链接，专门讨论这个以及各种优化。
作者: blackuhlan    时间: 2012-07-05 14:46
  1. switch(i)
  2. {
  3.    case 0x01:
  4.    case 0x02:
  5.    case 0x04:
  6.    case 0x08:
  7.    case 0x10:
  8.    ...
  9.       count = 1;
  10.    case 0x0003:
  11.    ...
  12.       count = 2;
  13.    ...
  14. }
  15. repeat and sum+=count;
复制代码
作者: fallening_cu    时间: 2012-07-06 06:44
回复 5# 塑料袋

分治这种方法最好只在面试的时候用来 sm 考官，自己用的时候还是老老实实地地查表吧
   
作者: safedead    时间: 2012-07-06 09:13
回复 10# blackuhlan


   

这个。。。
我咋感觉你这是单片机上的程序呢？
作者: sleepcat    时间: 2012-07-06 12:51
本帖最后由 sleepcat 于 2012-07-06 12:54 编辑

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    时间: 2012-07-06 15:59
1、11楼说的对，直接查表法是最快的。可以参考<编程之美>
2、10楼的需要N多判断的case会转化为一堆的if语句。
3、3楼的算法需要更高的条件，要求知道，并且通过数学验证的，算法效率还远不及查表算法快。
4、要求是最快的。
作者: captivated    时间: 2012-07-07 20:26
本帖最后由 captivated 于 2012-07-07 20:54 编辑

回复 5# 塑料袋


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


作者: starwing83    时间: 2012-07-07 21:19
本帖最后由 starwing83 于 2012-07-07 21:20 编辑

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;
}

这样不是更简单么= =
作者: 塑料袋    时间: 2012-07-07 22:42
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    时间: 2012-07-08 00:05
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    时间: 2012-07-08 05:53
回复 18# starwing83


    谁评估一下两个程序的运行性能？不就更有说服力么？
作者: 刘五十三    时间: 2012-07-08 12:53
最快就是直接用数字电路逻辑门，不可能还有比这更快的了。逻辑电路应该很简单。
作者: noword2k    时间: 2012-07-09 09:33
刘五十三 发表于 2012-07-08 12:53
最快就是直接用数字电路逻辑门，不可能还有比这更快的了。逻辑电路应该很简单。

没清茶和新闻了，失业了？
C/C++版块，扯数字电路逻辑门，这不瞎JB扯淡吗？
作者: selfrun    时间: 2012-07-09 14:13
A:位操作
    一次移位加法完成多个位的数据累加(对于32位整数，5次分别是16、8、4、2、1),时间复杂度是O(log(8*n))，编译器优化的最好结果是只有1次内存数据访问。
B:查表
    直接从内存取结果累加，不过cpu读内存也是顺序访问，时间复杂度是O(n),32位整数，至少4次内存访问。

曾经在intel 和amd处理器上比较过这两个方法，貌似一种处理器是A方法快，另一种处理器是B方法快。从复杂度分析上看，64位的应该是A方法好些

用循环的一定会变慢，因为分支预测失败，指令队列会被清空
作者: 群雄逐鹿中原    时间: 2012-07-09 15:15
刘五十三 发表于 2012-07-08 12:53
最快就是直接用数字电路逻辑门，不可能还有比这更快的了。逻辑电路应该很简单。


TTL门的响应时间在几个纳秒到几十纳秒，
CMOS门电路的响应时间更长，
算下来处理频率也就几十M到几百M，1G都不到。

你能搭出的很简单的逻辑电路，速度将会快不过当今一些常见的CPU。
而且你还得考虑如何处理输出输出，
你的输入输出能快过CPU cache的效能吗？

或者用FPGA或CPLD这些相对较复杂的编程逻辑器件？
作者: vhghhd    时间: 2012-07-10 09:31
int func(int x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
}
作者: 刘五十三    时间: 2012-07-17 12:35
群雄逐鹿中原 发表于 2012-07-09 15:15
TTL门的响应时间在几个纳秒到几十纳秒，
CMOS门电路的响应时间更长，
算下来处理频率也就几十M到几百M，1G都不到。

你能搭出的很简单的逻辑电路，速度将会快不过当今一些常见的CPU。
而且你还得考虑如何处理输出输出，
你的输入输出能快过CPU cache的效能吗？

或者用FPGA或CPLD这些相对较复杂的编程逻辑器件？


cpu本质就是逻辑门搭出来的。任何cpu的动作都是逻辑门的逻辑运算而已。逻辑门直接处理比cpu运算快几倍几十倍不是啥问题。就是你说的cpu cache，一样是逻辑门组成的。

比如以前的硬盘拷贝数据到内存，用dma比cpu快就是个例子，dma处理的时候，芯片直接接管总线然后挂起cpu,把数据拷贝到内存后再释放总线给cpu。
作者: 刘五十三    时间: 2012-07-17 12:46
noword2k 发表于 2012-07-09 09:33
没清茶和新闻了，失业了？
C/C++版块，扯数字电路逻辑门，这不瞎JB扯淡吗？

嗯，好在你又给我发了5毛。日子还过得去。你别老把啥都泛政治化，是不是要把我的方法打成五毛反动编程，然后再踏上一只脚，永世不得翻身啊。
作者: sb_oy    时间: 2012-07-17 13:00
还是4楼的算法比较犀利！
作者: 群雄逐鹿中原    时间: 2012-07-18 00:01
刘五十三 发表于 2012-07-17 12:35
cpu本质就是逻辑门搭出来的。任何cpu的动作都是逻辑门的逻辑运算而已。逻辑门直接处理比cpu运算快几倍几 ...


你这个是脱离现实的臆想而已。

这里逻辑门不是问题，我也相信你能搭出来。
问题在于工艺。相同的电路，在不同的工艺下，速度可是差距极大。
你搭出来的，和大规模集成电路工艺实现的，效果完全不一样。

作者: hshopeful    时间: 2012-08-30 15:53
回复 5# 塑料袋
您能把这段代码稍微解释一下吗？那些个掩码是怎么确定的！？谢谢！

   
作者: db1984    时间: 2012-08-30 16:35
定义一个表不就解决了吗

bitTable[256]={0,1,1,2,2,.........0~255的bit为1的数量}

32bit的整数

bitTable[x1] + bitTable[x2] + bitTable[x3] + bitTable[x4]
作者: mymtom_cu    时间: 2013-02-07 14:28
http://graphics.stanford.edu/~se ... l#CountBitsSetNaive
作者: freshxman    时间: 2013-02-07 16:24
提示: 作者被禁止或删除 内容自动屏蔽
作者: 蔡万钊    时间: 2013-02-07 19:40
循环中除2取余即可。可以处理任意位长的整数。
作者: ssfjhh    时间: 2013-02-08 08:51
本帖最后由 ssfjhh 于 2013-02-08 08:53 编辑

Python 乱入，保证在你敲完其它算法的代码前计算出结果。
  1. bin(i).count('1')
复制代码
作者: Crazy_bun    时间: 2013-03-25 13:10
回复 5# 塑料袋
你的速度是最快的。
其他人的代码拿个单片机跑跑就知道是垃圾代码了。


   
作者: anqiu1987    时间: 2013-07-18 17:02
不能用C++的bitset么。
作者: jonasan    时间: 2015-05-23 11:46
回复 5# 塑料袋

写的好啊，算法的复杂度是 log2(n) + 1，第一行其实是算每两个bit的1的个数，11-》2，10-》1，01-》1，00-》0，存储正好也是2个bit，剩下的是逐项合并，相邻 2 bit 相加，结果存为 4bit，相邻 4bit 相加，结果存为 8bit …… 最后得到1的个数。

写的很牛x！！

   
作者: wjn740    时间: 2015-12-30 10:56
回复 6# noword2k


    这个绝对是神贴！！！
作者: lxyscls    时间: 2015-12-31 10:01
1、查表
2、variable-precision SWAR
http://stackoverflow.com/questio ... war-algorithm-works



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2