| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
公告 |
One blog (or more) a day, keep bad mood away, and make life wonderful!
-- by 小生
Blog正在逐步成长中，小生与您共享思维火花，畅想IT时代！
|
| Blog信息 |
|
blog名称:小生杂谈
日志总数:166
评论数量:377
留言数量:1
访问次数:1010554
建立时间:2004年11月7日 |
| |
|
 [编程技术]判断32位整数二进制中1的个数
原创空间, 软件技术
Wonderow 发表于 2005/3/26 19:09:40 |
| 在面试中被问到这一题：判断32位无符号整数二进制中1的个数，虽然不难，但要求层层优化。现在整理一下： 1、基本思路：
500)this.width=500'>#include <iostream> 500)this.width=500'> 500)this.width=500'>using namespace std; 500)this.width=500'> 500)this.width=500'>500)this.width=500'>int findone(unsigned int n)500)this.width=500'>{ 500)this.width=500'> for(int i=0;n>0;n>>=1) 500)this.width=500'> i+=(n&1); 500)this.width=500'> return i; 500)this.width=500'>} 500)this.width=500'> 500)this.width=500'>500)this.width=500'>int main()500)this.width=500'>{ 500)this.width=500'> int n; 500)this.width=500'> cin>>n; 500)this.width=500'> cout<<findone(n)<<endl; 500)this.width=500'> return 0; 500)this.width=500'>} 2、优化： 这样的时间复杂度是T(m)=m，取决于二进制数的位数m。如果要求在更短时间内求出，应该如何做呢？如果findone函数被反复调用(成千上万次调用)，那应该怎么优化呢？ 其实就是空间换时间的思想：可以预建立一个表，存放了从0~2^32每个数中1的个数，用时去查一下表就知道了。但这样显然要耗费很多的空间（至少2^32/(256/32)=512MB，哈哈，正是一般内存大小）。于是需要再优化：存放0-255每个数中1的个数，然后分段查询。如下面把32位数分为4段，每段一个字节，所以有一个256大小供查询的表：
500)this.width=500'>char tOne[256]="\0\1\1\2\1\2……"; //后面省略 500)this.width=500'> 500)this.width=500'>500)this.width=500'>int findone(unsigned int n)500)this.width=500'>{ 500)this.width=500'> for(int i=0;n>0;n>>=8) 500)this.width=500'> i+=tOne[n&255]; 500)this.width=500'> return i; 500)this.width=500'>} 500)this.width=500'> 3、据说Intel中有条汇编指令（或是数条）即可完成这个工作，但不知道具体是什么，应该怎样做。4、又看到有道MS的笔试题殊途同归：
500)this.width=500'>500)this.width=500'>int func(unsigned int n)500)this.width=500'>{ 500)this.width=500'> int count=0; 500)this.width=500'>500)this.width=500'> while(n>0)500)this.width=500'>{ 500)this.width=500'> n&=(n-1); 500)this.width=500'> count++; 500)this.width=500'> } 500)this.width=500'> return count; 500)this.width=500'>} |
|
|
回复:判断32位整数二进制中1的个数
原创空间, 软件技术
外汇平台(游客)发表评论于2010/3/22 13:29:17 |
| 外汇平台相关连接：福汇平台 外汇平台 fxcm 福汇交易商 外汇交易商 福汇代理商 |
|
|
回复:判断32位整数二进制中1的个数
原创空间, 软件技术
外汇平台(游客)发表评论于2010/3/22 13:28:55 |
| 外汇平台相关连接：福汇平台 外汇平台 fxcm 福汇交易商 外汇交易商 福汇代理商 |
|
» 1 »
|