正文
ZT CSDN 如何以最快的速度计算出一个二进制数中1的个数? [
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
一道算法面试题:如何以最快的速度计算出一个二进制数中1的个数? [问题点数:10分,结帖人weicai_chen]收藏- weicai_chen
- weicai_chen
- 等级:
- 结帖率:95.12%
楼主 发表于: 2007-06-26 22:51:44 如何以最快的速度计算出一个二进制数中1的个数?假设这个二进制数位数可以很长,比如有100位以上或更多。。。
大家说说自己的想法。
更多
0
分享到:
相关主题推荐:
二进制
面试题
算法
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
回复次数:42
- HUNTON
- HUNTON
- 等级:
#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;
}
CSDN投诉事项说明 对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- oo
- oo
- 等级:
#2
得分:0
回复于:
2007-06-27 08:56:58
有个不用循环的算法,不过看不太懂
2014年1月微软MVP当选名单揭晓! 对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- SoftBomb
- SoftBomb
- 等级:
#3
得分:0
回复于:
2007-06-27 09:01:27
做个映射数组行不,以字节值为key,value就是对应的1的个数。然后就能8位8位的去统计了。
增加的时间就是建立映射数组的时间,在位数少(几千几万)的时候应该没有优势。更多了还行。
微软必应·英雄会第三届在线编程大赛 对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- fire_woods
- fire_woods
- 等级:
#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);
}
对我有用[1]
丢个板砖[0]
引用 |
举报 |管理
- ahjoe
- ahjoe
- 等级:
#5
得分:0
回复于:
2007-06-27 12:19:02
不用循环,可能吗?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- iceheart
- iceheart
- 等级:
#6
得分:1
回复于:
2007-06-27 13:52:04
http://www.everything2.com/index.pl?node_id=1181258
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- weicai_chen
- weicai_chen
- 等级:
#7
得分:0
回复于:
2007-06-27 18:14:51
哪位高手解释一下上面两个算法?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- guoshanhe
- guoshanhe
- 等级:
#8
得分:0
回复于:
2007-06-27 20:36:50
好题,mark
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- medie2005
- medie2005
- 等级:
3 #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。
详见《高效程序的奥秘》。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- jiangbin00cn
- jiangbin00cn
- 等级:
#10
得分:0
回复于:
2007-06-27 21:14:01
mark
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- lexchi
- lexchi
- 等级:
#11
得分:0
回复于:
2007-06-27 22:03:50
M
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- wxspll
- wxspll
- 等级:
#12
得分:0
回复于:
2007-06-28 02:47:48
mark
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- shu_yoyo
- shu_yoyo
- 等级:
#13
得分:0
回复于:
2007-06-28 13:21:42
mark一下
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- savagegan
- savagegan
- 等级:
#14
得分:0
回复于:
2007-06-28 14:21:35
mark
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- xiaocai0001
- xiaocai0001
- 等级:
32 #15
得分:0
回复于:
2007-06-28 15:13:12
高效程序的奥秘里提到过...
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- yy_msdn
- yy_msdn
- 等级:
#16
得分:0
回复于:
2007-07-22 20:56:03
但是他那个数可能是100位啊?int能装的下吗?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- NowCan
- NowCan
- 等级:
#17
得分:0
回复于:
2007-07-22 21:46:56
按4字节分组啊。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- yy_msdn
- yy_msdn
- 等级:
#18
得分:0
回复于:
2007-07-22 21:58:39
把它当作字符串来处理吗?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- zhuying1983
- zhuying1983
- 等级:
#19
得分:0
回复于:
2007-07-23 10:27:46
number &= (number - 1
好方法 ,佩服佩服
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- SoftBomb
- SoftBomb
- 等级:
#20
得分:0
回复于:
2007-07-23 11:51:17
快速将所有的1都置零,NB
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- gxqcn
- gxqcn
- 等级:
#21
得分:0
回复于:
2007-07-23 13:36:52
我前不久查阅了 Intel 的技术资料,Intel SSE4 新增了“POPCNT”指令,
一条指令即可获得 16/32/64 bits 中含有 bits set to 1 的数目,
若用它,以上所有技巧都将相形失色。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- fire_woods
- fire_woods
- 等级:
#22
得分:0
回复于:
2007-07-23 15:58:39
俺做ARM的.
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- gxqcn
- gxqcn
- 等级:
#23
得分:0
回复于:
2007-07-23 17:09:05
我也写ARM程序(并用DSP)。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- fire_woods
- fire_woods
- 等级:
#24
得分:0
回复于:
2007-07-23 17:26:42
我暂时不用DSP
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- settingsun86
- settingsun86
- 等级:
#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;
}
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- bao110908
- bao110908
- 等级:
456 #26
得分:0
回复于:
2007-07-24 10:53:00
fire_woods 的方法很好,说细的算法说明可以参看《Hacker's Delight》(中文书名《高效程序的奥秘》)里面有讲解。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- jiangbin00cn
- jiangbin00cn
- 等级:
#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,
高效,异读,就是浪费内存。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- whycadi
- whycadi
- 等级:
#28
得分:0
回复于:
2007-07-25 22:02:36
fire_woods(风林火山)的算法不错,两两合并求1的个数的和,虽然32位上优势不大,如果是64位的话就比移位快很多了。比查表省地方多了。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- krfstudio
- krfstudio
- 等级:
#29
得分:0
回复于:
2007-07-26 17:03:34
MARK,学到不少东西,呵呵。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- sankt
- sankt
- 等级:
#30
得分:0
回复于:
2007-07-26 23:48:37
比较经典的问题了
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- trueytht
- trueytht
- 等级:
#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) 就行了.
大家都怎么实现把长串分割的呢?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- jiangbin00cn
- jiangbin00cn
- 等级:
#33
得分:0
回复于:
2007-08-15 22:25:48
1000万的0/1输入
//////////////////////////
这里不明白,计算机内部数据都是以字节为单位的,1000万个0/1输入,每个0/1占一个字节?这样的话是你之前处理的问题,而不是这个算法的问题
个人认为就速度而言造表法最快,不过如果是嵌入式开发两两合并求1的算法最优,关键是能够拓展思路
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- NowCan
- NowCan
- 等级:
#34
得分:0
回复于:
2007-08-16 12:49:48
1000万个0/1输入,每个0/1占一个字节?
==
是啊我也糊涂了,如果这样的话,直接扫描一遍就很快了。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- NowCan
- NowCan
- 等级:
#35
得分:0
回复于:
2007-08-16 12:50:28
直接相加就够了。
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- trueytht
- trueytht
- 等级:
#36
得分:0
回复于:
2007-08-16 19:49:15
看来我是没明白原题的意思,该算法的输入是什么呢?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- ahjoe
- ahjoe
- 等级:
#37
得分:0
回复于:
2007-08-19 15:08:06
按Byte查表, 不只一个字节就循环
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- DLMU_net
- DLMU_net
- 等级:
#38
得分:0
回复于:
2007-08-22 15:02:51
mark~
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- lzxwyh
- lzxwyh
- 等级:
#39
得分:0
回复于:
2007-08-26 22:25:30
把0替换掉,剩下的长度不就是1的个数么?
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- hehehengha1
- hehehengha1
- 等级:
#40
得分:0
回复于:
2009-10-10 00:17:57
咋和低位的没啥区别 都是循环移位的??
高手给个意见罗
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- ccm_0
- ccm_0
- 等级:
#41
得分:0
回复于:
2010-09-23 17:10:39
学习一下
对我有用[0]
丢个板砖[0]
引用 |
举报 |管理
- lj836263698
- lj836263698
- 等级:
#42
得分:0
回复于:
2010-09-28 18:49:41
我来挺挺!!!!!!!!!!1我来挺挺!!!!!!!!!!1
楼主 发表于: 2007-06-26 22:51:44 如何以最快的速度计算出一个二进制数中1的个数?假设这个二进制数位数可以很长,比如有100位以上或更多。。。 大家说说自己的想法。 更多 分享到: 相关主题推荐: 二进制 面试题 算法 | ||
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 回复次数:42 |
| #1 回复于: 这个不是前一段那个101个面试题中的一题吗。 计算整数number的比特位值为1的位数 int getBits(int number) for( ; number; number &= number - 1) | |
CSDN投诉事项说明 对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #2 回复于: 有个不用循环的算法,不过看不太懂 | |
2014年1月微软MVP当选名单揭晓! 对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #3 回复于: 做个映射数组行不,以字节值为key,value就是对应的1的个数。然后就能8位8位的去统计了。 | |
微软必应·英雄会第三届在线编程大赛 对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #4 回复于: unsigned int | |
对我有用[1] 丢个板砖[0] 引用 | 举报 | 管理 |
| #5 回复于: 不用循环,可能吗? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #6 回复于: http://www.everything2.com/index.pl?node_id=1181258 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #7 回复于: 哪位高手解释一下上面两个算法? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #8 回复于: 好题,mark | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| 3 #9 回复于: 关键是:number &= (number - 1) 讨论之。 1):number 为奇数,则number &= (number - 1)萃取末尾1,并将结果赋给number。计数器显然要加1。 详见《高效程序的奥秘》。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #10 回复于: mark | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #11 回复于: M | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #12 回复于: mark | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #13 回复于: mark一下 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #14 回复于: mark | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| 3 2 #15 回复于: 高效程序的奥秘里提到过... | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #16 回复于: 但是他那个数可能是100位啊?int能装的下吗? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #17 回复于: 按4字节分组啊。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #18 回复于: 把它当作字符串来处理吗? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #19 回复于: number &= (number - 1 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #20 回复于: 快速将所有的1都置零,NB | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #21 回复于: 我前不久查阅了 Intel 的技术资料,Intel SSE4 新增了“POPCNT”指令, | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #22 回复于: 俺做ARM的. | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #23 回复于: 我也写ARM程序(并用DSP)。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #24 回复于: 我暂时不用DSP | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #25 回复于: int GetBits(int number) for(; number >0; number/=2) return retval; | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| 4 5 6 #26 回复于: fire_woods 的方法很好,说细的算法说明可以参看《Hacker's Delight》(中文书名《高效程序的奥秘》)里面有讲解。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #27 回复于: int getBits(int number) for( ; number; number &= number - 1) //////////////////////// 如果内存宽裕,可以造表,呵呵,我是tablelover, | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #28 回复于: fire_woods(风林火山)的算法不错,两两合并求1的个数的和,虽然32位上优势不大,如果是64位的话就比移位快很多了。比查表省地方多了。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #29 回复于: MARK,学到不少东西,呵呵。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #30 回复于: 比较经典的问题了 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #31 回复于: 问一下具体的实现,现在我知道了32bit的好方法: const int MASK1 = 0x55555555; n = (n & MASK1) + ((n >> 1) & MASK1); cout << n << " number of 1." << endl; 但是对于长度是1000万的0/1输入,如何实现呢? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #33 回复于: 1000万的0/1输入 个人认为就速度而言造表法最快,不过如果是嵌入式开发两两合并求1的算法最优,关键是能够拓展思路 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #34 回复于: 1000万个0/1输入,每个0/1占一个字节? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #35 回复于: 直接相加就够了。 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #36 回复于: 看来我是没明白原题的意思,该算法的输入是什么呢? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #37 回复于: 按Byte查表, 不只一个字节就循环 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #38 回复于: mark~ | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #39 回复于: 把0替换掉,剩下的长度不就是1的个数么? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #40 回复于: 咋和低位的没啥区别 都是循环移位的?? | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #41 回复于: 学习一下 | |
对我有用[0] 丢个板砖[0] 引用 | 举报 | 管理 |
| #42 回复于: 我来挺挺!!!!!!!!!!1我来挺挺!!!!!!!!!!1 |