如何以最快的速度计算出一个二进制数中1的个数？假设这个二进制数位数可以很长，比如有100位以上或更多。。。

大家说说自己的想法。

回复次数：42

#1
得分：3

回复于：
2007-06-27 08:47:25

这个不是前一段那个101个面试题中的一题吗。

计算整数number的比特位值为1的位数

int getBits(int number)
{
    int retval = 0;

for( ; number; number &= number - 1)
        retval++;
    return retval;
}

#2
得分：0

回复于：
2007-06-27 08:56:58

有个不用循环的算法，不过看不太懂

#3
得分：0

回复于：
2007-06-27 09:01:27

做个映射数组行不，以字节值为key，value就是对应的1的个数。然后就能8位8位的去统计了。
增加的时间就是建立映射数组的时间，在位数少（几千几万）的时候应该没有优势。更多了还行。

#4
得分：3

回复于：
2007-06-27 09:13:05

unsigned int
ones32(register unsigned int x)
{
        /* 32-bit recursive reduction using SWAR...
   but first step is mapping 2-bit values
   into sum of 2 1-bit values in sneaky way
*/
        x -= ((x >> 1) & 0x55555555);
        x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
        x = (((x >> 4) + x) & 0x0f0f0f0f);
        x += (x >> 8);
        x += (x >> 16);
        return(x & 0x0000003f);
}

#5
得分：0

回复于：
2007-06-27 12:19:02

不用循环，可能吗？

#6
得分：1

回复于：
2007-06-27 13:52:04

http://www.everything2.com/index.pl?node_id=1181258

#7
得分：0

回复于：
2007-06-27 18:14:51

哪位高手解释一下上面两个算法？

#8
得分：0

回复于：
2007-06-27 20:36:50

好题，mark

#9
得分：3

回复于：
2007-06-27 21:03:24

关键是：number &= (number - 1)

讨论之。

1)：number 为奇数，则number &= (number - 1)萃取末尾1，并将结果赋给number。计数器显然要加1。
2)：number 为偶数，则number &= (number - 1)number最末尾的1置成0，其余不变，并将结果赋给number。若此时number不为0，则说明仍可继续，由于已经将number最末尾的1置成0，因此，计数器也要加1。

详见《高效程序的奥秘》。

#10
得分：0

回复于：
2007-06-27 21:14:01

mark

#11
得分：0

回复于：
2007-06-27 22:03:50

M

#12
得分：0

回复于：
2007-06-28 02:47:48

mark

#13
得分：0

回复于：
2007-06-28 13:21:42

mark一下

#14
得分：0

回复于：
2007-06-28 14:21:35

mark

#15
得分：0

回复于：
2007-06-28 15:13:12

高效程序的奥秘里提到过...

#16
得分：0

回复于：
2007-07-22 20:56:03

但是他那个数可能是100位啊？int能装的下吗？

#17
得分：0

回复于：
2007-07-22 21:46:56

按4字节分组啊。

#18
得分：0

回复于：
2007-07-22 21:58:39

把它当作字符串来处理吗？

#19
得分：0

回复于：
2007-07-23 10:27:46

number &= (number - 1
好方法 ，佩服佩服

#20
得分：0

回复于：
2007-07-23 11:51:17

快速将所有的1都置零，NB

#21
得分：0

回复于：
2007-07-23 13:36:52

我前不久查阅了 Intel 的技术资料，Intel SSE4 新增了“POPCNT”指令，
一条指令即可获得 16/32/64 bits 中含有 bits set to 1 的数目，
若用它，以上所有技巧都将相形失色。

#22
得分：0

回复于：
2007-07-23 15:58:39

俺做ARM的.

#23
得分：0

回复于：
2007-07-23 17:09:05

我也写ARM程序（并用DSP）。

#24
得分：0

回复于：
2007-07-23 17:26:42

我暂时不用DSP

#25
得分：0

回复于：
2007-07-24 10:24:32

int GetBits(int number)
{
int retval = 0;

for(; number >0; number/=2)
{
if((number % 2) == 1)
retval ++;
}

return retval;
}

#26
得分：0

回复于：
2007-07-24 10:53:00

fire_woods 的方法很好，说细的算法说明可以参看《Hacker's Delight》（中文书名《高效程序的奥秘》）里面有讲解。

#27
得分：0

回复于：
2007-07-24 21:48:00

int getBits(int number)
{
    int retval = 0;

for( ; number; number &= number - 1)
        retval++;
    return retval;
}

////////////////////////
mark

如果内存宽裕，可以造表，呵呵，我是tablelover,
高效,异读，就是浪费内存。

#28
得分：0

回复于：
2007-07-25 22:02:36

fire_woods(风林火山)的算法不错，两两合并求１的个数的和，虽然３２位上优势不大，如果是６４位的话就比移位快很多了。比查表省地方多了。

#29
得分：0

回复于：
2007-07-26 17:03:34

MARK，学到不少东西，呵呵。

#30
得分：0

回复于：
2007-07-26 23:48:37

比较经典的问题了

#31
得分：0

回复于：
2007-08-13 20:38:08

问一下具体的实现,现在我知道了32bit的好方法:
void find32One(int n) {

const int MASK1 = 0x55555555;
        const int MASK2 = 0x33333333;
        const int MASK4 = 0x0f0f0f0f;
        const int MASK8 = 0x00ff00ff;
        const int MASK16 = 0x0000ffff;

n = (n & MASK1) + ((n >> 1) & MASK1);
n = (n & MASK2) + ((n >> 2) & MASK2);
n = (n & MASK4) + ((n >> 4) & MASK4);
n = (n & MASK8) + ((n >> 8) & MASK8);
n = (n & MASK16) + ((n >> 16) & MASK16);

cout << n << " number of 1." << endl;
}

但是对于长度是1000万的0/1输入,如何实现呢?
如果用string来存储每一个32bit,那效率是不是太低了?
要不然如何去实现呢?所以我觉得这个算法的主要开销在前面,
而不是32bit的.既然主要开销在前面,那应该集中去处理
前面的部分,32bit这里用移位或者n &= (n-1) 就行了.
   大家都怎么实现把长串分割的呢?

#33
得分：0

回复于：
2007-08-15 22:25:48

1000万的0/1输入
//////////////////////////
这里不明白，计算机内部数据都是以字节为单位的，1000万个0/1输入，每个0/1占一个字节？这样的话是你之前处理的问题，而不是这个算法的问题

个人认为就速度而言造表法最快，不过如果是嵌入式开发两两合并求１的算法最优，关键是能够拓展思路

#34
得分：0

回复于：
2007-08-16 12:49:48

1000万个0/1输入，每个0/1占一个字节？
＝＝
是啊我也糊涂了，如果这样的话，直接扫描一遍就很快了。

#35
得分：0

回复于：
2007-08-16 12:50:28

直接相加就够了。

#36
得分：0

回复于：
2007-08-16 19:49:15

看来我是没明白原题的意思,该算法的输入是什么呢?

#37
得分：0

回复于：
2007-08-19 15:08:06

按Byte查表, 不只一个字节就循环

#38
得分：0

回复于：
2007-08-22 15:02:51

mark~

#39
得分：0

回复于：
2007-08-26 22:25:30

把0替换掉，剩下的长度不就是1的个数么？

#40
得分：0

回复于：
2009-10-10 00:17:57

咋和低位的没啥区别 都是循环移位的？？
高手给个意见罗

#41
得分：0

回复于：
2010-09-23 17:10:39

学习一下

#42
得分：0

回复于：
2010-09-28 18:49:41

我来挺挺！！！！！！！！！！1我来挺挺！！！！！！！！！！1