统计数的二进制表示中1的个数 - 简书
统计数的二进制表示中1的个数
题目：给定一个非负整数num，求0&=i&=num的每个整数的二进制数中一的个数
很简单就能想到使用builtin函数求解，但是很不幸这个方案被ban掉了，并且要求我们要能在一次遍历中求出结果。仔细观察结果产生的规律，我们没有必要每一次求解都将整个整数的二进制位遍历一次，只需利用已经计算出的结果和改数的最高位即可计算出结果。比如对数10101而言，看除第一位外的数值为5，显然此时1的二进制表达中5的位数已经求出来了了，于是乎我们只需要将这个结果加上1就可以了。还有一个问题是如何方便的确定减数的大小。假定减数设定为s，则s必定为2的幂，则在s 至 2s - 1中间的数都应该减去s再查表中的结果，当循环计数器i等于2s时，则将s扩大一倍，直到循环结束。具体的C语言实现如下：
int *countBits(int num, int *returnSize) {
int *ret = malloc(sizeof(int) * (++num));
ret[0] = 0;
int begin = 0, sum = 1;
for (int i = 1; i & i++) {
if (i == sum) {
ret[i] = 1;
int off = i -
if (off) {
ret[i] = 1 + ret[off];
ret[i] = ret[off];
*returnSize =
我和C++的门槛怼了起来本帖子已过去太久远了，不再提供回复功能。扫二维码下载作业帮
1.75亿学生的选择
下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
一个数如何用二进制表示?十进制可以这样表示203.49,那二进制也可以这样表示吗?能写出来给我看看吗?
扫二维码下载作业帮
1.75亿学生的选择
首先,你要确定你要用二进制表示的数是几进制.第二步,把这个数化成10进制的数.第三步,把这个数化成2进制数.化法如下：（整数,小数这里不写了,类似）如10进制的1212/2=6 余06/2 = 3 余03/2=1余1结果就是1100
我的意思是十进制可以按照我图上的式子表达，二进制可以这样表示吗？
比如：2进制数
=1 × 2^5 + 1 × 2^4 + 0×2³ + 1×2² + 0×2^1 + 1×2^0 (转化为10进制数)
203.49可以吗？
表示为2进制？
先做整数部分
203(D) = (B)
再做小数部分:
由于小数部分位数与小数的关系:
第1位 1 - 0.5(10进制，即2^(-1))
第2位 1 - 0.25(10进制，即2^(-2))
第3位 1 - 0.125(10进制，即2^(-3))
第4位 1 - 0.0625(10进制，即2^(-3))
而0.49 0.25 第2位为1, 0.49-0.25 = 0.24
0.24>0.125，第3位为1,0.24-0.125=0.115
0.115>0.0625,第4位为1, 0.115-0.0625=...
然后再按这个规律计算下去。
保留到小数第4位，结果就是：
203.49(D)=1(B)
（由于很难做到把小数位完全用0,1这样数表示出来，所以计算机存在误差）
× 2^5 + 1 × 2^4 + 0×2³ + 1×2² + 0×2^1 + 1×2^0可以这样表示那203.49呢？也可以这样表示吗？
上面不是有了吗？
0.49=.0111(B) =0*2^(-1) + 1 * 2^(-2) + 1* 2^(-3) + 1 * 2^(-4)
一定要先转换成1？
不转换的话，如何知道哪一位上是0，哪一位上是1?
为您推荐：
其他类似问题
扫描下载二维码求一个数二进制表示法中1的个数诸多方法
我的图书馆
求一个数二进制表示法中1的个数诸多方法
求一个unsigned int 数的二进制表示中有多少个1？这是一道面试题可以用以下的一些方案。第一种是很容易想到的采用循环的方式并且与1进行位与运算，具体代码如下。
1unsigned int GetBitNumOfOne_ByLoop1(unsigned int nValue)2{3 const unsigned int nNumOfBitInByte = 8;4 unsigned int nBitMask = 1;5 unsigned int nBitNum = 0;6 for(unsigned int i = 0 ; i & sizeof(nValue) * nNumOfBitInB i++)7 {8 (0 & (nValue & nBitMask)) ? nBitNum++ : 0;9 nBitMask&&=1;10 }11 return nBitN12}13unsigned int GetBitNumOfOne_ByLoop2(unsigned int nValue)14{15 const unsigned int nNumOfBitInByte = 8;16 unsigned int nBitMask = 1;17 unsigned int nBitNum = 0;18 for(unsigned int i = 0 ; i & sizeof(nValue) * nNumOfBitInB i++)19 {20 (0 & (nValue & nBitMask)) ? nBitNum++ : 0;21 nValue&&=1;22 }23 return nBitN24}
这两种做法很相像，却别就是在是对nBitMask进行左移还是对nValue进行右移。当然了以上的两个方法存在一个问题：不管如何这个函数肯定要循环32次（对于32平台来说）。那又没有更好的方法？当然有，请看下面：1unsigned int GetBitNumOfOne_ByLoop3(unsigned int nValue)2{3 unsigned int nBitNum = 0;4 while(0 & nValue)5 {6 nValue &=(nValue - 1);7 nBitNum++;8 }9 return nBitN10}
假如使用参数12345（二进制是01）调用该函数，该函数的执行情况如下：第一次进入循环0 & 0101 &= (01 - 1) 之后 nValue 的值 是 00nBitNum 的值是1经过本次循环之后01 变成了 00 比之前少了一个1第二次进入循环0 & 0000 &= (00 - 1) 之后 nValue 的值 是 00nBitNum 的值是2经过本次循环之后00 变成了 00 比之前少了一个1第三次进入循环0 & 0000 &= (00 - 1) 之后 nValue 的值 是 00nBitNum 的值是3经过本次循环之后00 变成了 00 比之前少了一个1经过以上3次循环情况的说明，我相信你一定看出了些什么吧。nValue &=(nValue - 1)，这句代码实际上就是把nValue 的某位及其以后的所有位都变成0，当nValue最后变成0的时候循环结束，且nBitNum 记录的就是1的个数。上面的做法已经很不错了，但是作为程序员的你是否会有疑问，"还有其他的方法吗？"。有，当然有！请看下面的代码：1unsigned int GetBitNumOfOne(unsigned int nValue)2{3 nValue = ((0xaaaaaaaa & nValue)&&1) + (0x & nValue);4 nValue = ((0xcccccccc & nValue)&&2) + (0x & nValue);5 nValue = ((0xf0f0f0f0 & nValue)&&4) + (0x0f0f0f0f & nValue);6 nValue = ((0xff00ff00 & nValue)&&8) + (0x00ff00ff & nValue);7 nValue = ((0xffff0000 & nValue)&&16) + (0x0000ffff & nValue);8 9 return nV10}
假如你是第一次看到这些代码，你是否能看明白？呵呵，本人第一次看到这些代码的时候看了好久才感觉好像有点明白。下面我就以一个例子来说明上面的代码是如何做到的。假如参数是0xffffffff。第一行代码：nValue = ((0xaaaaaaaa & nValue)&&1) + (0x & nValue);a的二进制表示是：10105的二进制表示是：01010xffffffff 与 0xaaaaaaaa 进行与运算之后是0x然后再进行左移操作后是0x0x & nValue 进行与运算之后是0x然后0x & 0x得到0x我们把得到的结果分成16组0x10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10每组的10单独来看是不是十进制的2我们0xx这两个数也按照上面的方法分成16个组0x01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 010x01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01那么这两个数的每一个组都是01 那么两个01 里面有几个1，是不是2个。这是2是不是二进制的10，然后16个10组合起来是不是0x
第二行代码：nValue = ((0xcccccccc & nValue)&&2) + (0x & nValue);此时nValue是0xc的二进制表示是：11003的二进制表示是：00110xcccccccc 与 nValue) 进行与运算之后是0x然后再进行左移操作后是0x0x & nValue 进行与运算之后是0x
然后0x & 0x得到0x我们把得到的结果分成8组0x00 00 每组的0100单独来看是不是十进制的4 总共有多少个4？是不是8个，8×4=32。
以下的代码：nValue = ((0xf0f0f0f0 & nValue)&&4) + (0x0f0f0f0f & nValue);nValue = ((0xff00ff00 & nValue)&&8) + (0x00ff00ff & nValue);nValue = ((0xffff0000 & nValue)&&16) + (0x0000ffff & nValue);请自己按照上面的方法做一遍，就会发现规律：第一次32位数分成32组，第二次分成16组，第三次分成8，第四次分成4，第五次分成2组。如果还是不明白请多看看，然后多选择几个参数进行试验，多试几次肯定会明白的。
看了这么多解法是不是有中很过瘾的感觉，当我知道有这么多解法是也很过瘾，也很遗憾。遗憾什么呢？遗憾当时我碰到这道面试题的时候只想到了采用循环的方法，可是那个面试题上明确说明不准使用循环！！当时很郁闷！！郑重声明：上面最后两个解法非本人原创，本人只是总结归纳，向想出这么好方法的前辈高人致敬！
TA的最新馆藏[转]&[转]&