题目:给定一个无符号32位整数x,求x的二进制表示法中含1的个数?
第一种算法:
int OneCount(unsigned int x)
{
for(int count=0; x>0; count++)
x&=x-1;//把最后面的1变0
return count;
}
上面算法的时间复杂度就是1的个数。
第二种算法(查表法):
const int idx[256]={0,1,1,,8}//0~255中含1的个数
int OneCount(unsigned int x)
{
int count=0;
for(; x>0; x>>=8)
count+=idx[x&255];
return count;
}
上面算法最多只需要4次循环,用空间换取时间。
第二种算法的另一种形式:
const int idx[256]={0,1,1,..,8}
int OneCount(unsigned int x)
{
unsigned char* p=(unsigned char*)&x;
return idx[*p]+idx[*(p+1)]+idx[*(p+2)]+idx[*(p+3)];
}
第三种算法:
int OneCount(unsigned int x)
{
x=(x&0x55555555UL)+((x>>1)&0x55555555UL); //1
x=(x&0x33333333UL)+((x>>2)&0x33333333UL);//2
x=(x&0x0f0f0f0fUL)+((x>>4)&0x0f0f0f0fUL); //3
x=(x&0x00ff00ffUL)+((x>>8)&0x00ff00ffUL); //4
x=(x&0x0000ffffUL)+((x>>16)&0x0000ffffUL);//5
return x;
}
解释:比如对于一个8位的整数122,用二进制表达0111 1010(abcd efgh),第1行代码的功能是x=0b0d 0f0h+0a0c 0e0g,两位一组,分别计算四组(a,b; c,d; e,f; g,h; )中1的个数,本例中x=0101 0000+0001 0101=0110 0101(更新的abcd efgh),在此基础上,再分组,就是第二行的功能x=00cd 00gh+00ab 00ef,四位一组(abcd; efgh),分别计算这两组包含1的个数,本例中x=0010 0001+0001 0001=0011 0010(更新abcd efgh),再8位一组,如第三行所示,x=0000 efgh+0000abcd=0000 0010+0000 0011=0000 0101=5,所以该整数122共包含5个1。
本算法思想:归并,对于一个32位的整数,先分成16组,统计每组(2位)中1的个数,再将统计的结果两两合并,得到8组,在此基础上又合并得到4组,2组,1组,进而得到最终结果。
分享到:
相关推荐
题目输入一个整数,输出该数32位二进制表示中1的个数(其中负数用补码表示)示例输入输出题解二进制移位法//将 mark0x01 和 n 进行 ‘&’ 运算//
题目:给定一个无符号32位整数num,求num的二进制表示法中含1的个数。提供了8中实现方式。
特点 :将 a 和 b 先转换为二进制,按位比较,对应位置的数字都为1的话,那么该位的整体结果为1,否则就为0 ex:5 & 3 5 :101 3 :011 =========== 001 结果 :1 使用场合:任意数字与1做按位与操作,可以...
说明:输入的第1个数表示学生人数(n=9),接着输入的9个成绩中,累加和为628.5(所有小数均保留一位小数输出),平均分为69.8分;平均分以上(A档)有4人,占44.4%,平均分以下(B档)有5人,占55.6%;A档的最低...
第1章 C语言概述 1 1.5 参照本章例题,编写一个C程序,输出以下信息: 1 1.6 写一个程序,输入a,b,c三个值,输出其中最大者。 1 第2章 程序的灵魂——算法 2 2.1 什么叫结构化的算法?为什么要提倡结构化的算法? 2 ...
11.3.1 用n的二进制分解式计算xn 250 11.3.2 用Fortran语言计算2n 251 11.4 整数对数 252 11.4.1 以2为底的整数对数 253 11.4.2 以10为底的整数对数 253 11.5 习题 257 第12章 以特殊值为底的数制 258 12.1 ...
├─053 查找整数二进制中1的个数 ├─054 DNA子串 ├─055 MP3光标位置 │ └─Source │ └─Debug ├─056 查找2个字符串最大相同子串 │ └─Debug ├─057 配置文件恢复 │ └─Source │ └─Debug ├─058 24...
本书从函数功能、函数格式、参数说明、注意事项、Excel 版本提醒、案例应用、交叉参考7 个方面,全面、细致地介绍了Excel 2016/2013/2010/2007/2003 中公式和函数的使用方法、实际应用和操作技巧。最后3 章还将公式...
1.4.10. 统计整数二进制表示中 1 的个数........................................................102 1.5. 面试题集合(四) ....................................................................................
<br>实验二 单链表结构及计算 实验目的: 通过实验掌握下列知识: 1、熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现; 2、继续熟悉VC编程、编译和调试环境; 内容及步骤:...
有 5种表示方式:3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+1。 ①以下是该函数的程序段,请将未完成的部分填入,使之完整 int f(m,n) int m,n; { if(m==1) return (1) ; if(n==1){ return (2) ;} if(m) {...
用十进制整数来表示输出的最少位数。 若实际位数多于定义的宽度,则按实际位数输出, 若实际位数少于定义的宽度则补以空格或0。 4.精度 精度格式符以“.”开头,后跟十进制整数。本项的意义是:如果输出数字,则表示...
这导致空间浪费而且无法与外部数据文件进行“二进制”读写。能否关掉填充,或者控制结构域的对齐方式? 2.14 为什么sizeof返回的值大于结构大小的期望值,是不是尾部有填充? 2.15 如何确定域在结构中的字节偏移...
这导致空间浪费而且无法与外部数据文件进行“二进制”读写。能否关掉填充,或者控制结构域的对齐方式? 27 2.14 为什么sizeof返回的值大于结构大小的期望值,是不是尾部有填充? 28 2.15 如何确定域在结构中的...
实例043 将二维数组中的行列互换 53 实例044 利用数组随机抽取幸运观众 54 实例045 用数组设置JTable表格的列名与列宽 55 3.2 数组操作 57 实例046 数组的下标界限 57 实例047 按钮控件数组实现计数器界面 58 实例...