算是上一篇的续集

[算法]计算某正整数换算成二进制后bit为1的个数

电子技术 IT Tech, 算法 Algorithm, 网络转载 Reprint

by Jian Xu

//顺便求推荐：如何在WordPress中插入格式化的带语法高亮的代码或者数学公式，如果你知道的话，请直接在下面留言，谢谢~

侃哥在准备去Cisco的面试，问我一道题：求二进制数中1的个数。

看起来简单，不假思索地写下了

num=0;
while(x)
{
num+=x&1;
x>>1;
}

位运算，似乎已经够简单了。问我还有没有更简单的解法，我想了会儿没想出来，但我觉得应该有。网上一搜，就被一个巧妙的算法震惊了：

num=0;

while(x)
{
x &= (x-1);
num++;
}

相比我的算法，只有一点点改动；但我的算法循环的次数是和原数log 2相关的，而这个算法的循环次数只与原数中bit为1的数目相关，这样，它的循环次数必定少于我的。

果然大长见识。在网上仔细搜了搜，发现好多神奇的算法，虽然没能全看懂，不过摘录几篇，大家一起学习学习~

/************ 第一篇 **************/

对于一个字节（8bit）的变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能地高。

大多数的读者都会有这样的反应：这个题目也太简单了吧，解法似乎也相当地单一，不会有太多的曲折分析或者峰回路转之处。那么面试者到底能用这个题目考察我们什么呢？事实上，在编写程序的过程中，根据实际应用的不同，对存储空间或效率的要求也不一样。比如在PC上的程序编写与在嵌入式设备上的程序编写就有很大的差别。我们可以仔细思索一下如何才能使效率尽可能地“高”。

【解法一】

可以举一个八位的二进制例子来进行分析。对于二进制操作，我们知道，除以一个2，原来的数字将会减少一个0。如果除的过程中有余，那么就表示当前位置有一个1。

以10 100 010为例；

第一次除以2时，商为1 010 001，余为0。

第二次除以2时，商为101 000，余为1。

因此，可以考虑利用整型数据除法的特点，通过相除和判断余数的值来进行分析。于是有了如下的代码。

代码清单2-1

int Count(int v)

{

int num = 0;

while(v)

{

if(v % 2 == 1)

{

num++;

}

v = v/ 2;

}

return num;

}

【解法二】使用位操作

前面的代码看起来比较复杂。我们知道，向右移位操作同样也可以达到相除的目的。唯一不同之处在于，移位之后如何来判断是否有1存在。对于这个问题，再来看看一个八位的数字：10 100 001。

在向右移位的过程中，我们会把最后一位直接丢弃。因此，需要判断最后一位是否为1，而“与”操作可以达到目的。可以把这个八位的数字与00000001进行“与”操作。如果结果为1，则表示当前八位数的最后一位为1，否则为0。代码如下：

代码清单2-2

int Count(int v)

{

int num = 0;

While(v)

{

num += v &0×01;

v >>= 1;

}

return num;

}

【解法三】

位操作比除、余操作的效率高了很多。但是，即使采用位操作，时间复杂度仍为O（log₂v），log₂v为二进制数的位数。那么，还能不能再降低一些复杂度呢？如果有办法让算法的复杂度只与“1”的个数有关，复杂度不就能进一步降低了吗？

同样用10 100 001来举例。如果只考虑和1的个数相关，那么，我们是否能够在每次判断中，仅与1来进行判断呢？

为了简化这个问题，我们考虑只有一个1的情况。例如：01 000 000。

如何判断给定的二进制数里面有且仅有一个1呢？可以通过判断这个数是否是2的整数次幂来实现。另外，如果只和这一个“1”进行判断，如何设计操作呢？我们知道的是，如果进行这个操作，结果为0或为1，就可以得到结论。

如果希望操作后的结果为0，01 000 000可以和00 111 111进行“与”操作。

这样，要进行的操作就是 01 000 000 &（01 000 000 – 00 000 001）= 01 000 000 &
00 111 111 = 0。

因此就有了解法三的代码：

代码清单2-3

int Count(int v)

{

int num = 0;

while(v)

{

v &= (v-1);

num++;

}

return num;

}

【解法四】使用分支操作

解法三的复杂度降低到O（M），其中M是v中1的个数，可能会有人已经很满足了，只用计算1的位数，这样应该够快了吧。然而我们说既然只有八位数据，索性直接把0~255的情况都罗列出来，并使用分支操作，可以得到答案，代码如下：

代码清单2-4

int Count(int v)

{

int num = 0;

switch (v)

{

case 0×0:

num = 0;

break;

case 0×1:

case 0×2:

case 0×4:

case 0×8:

case 0×10:

case 0×20:

case 0×40:

case 0×80:

num = 1;

break;

case 0×3:

case 0×6:

case 0xc:

case 0×18:

case 0×30:

case 0×60:

case 0xc0:

num = 2;

break;

//…

}

return num;

}

解法四看似很直接，但实际执行效率可能会低于解法二和解法三，因为分支语句的执行情况要看具体字节的值，如果a =0，那自然在第1个case就得出了答案，但是如果a =255，则要在最后一个case才得出答案，即在进行了255次比较操作之后！

看来，解法四不可取！但是解法四提供了一个思路，就是采用空间换时间的方法，罗列并直接给出值。如果需要快速地得到结果，可以利用空间或利用已知结论。这就好比已经知道计算1+2+ … +N的公式，在程序实现中就可以利用公式得到结论。

最后，得到解法五：算法中不需要进行任何的比较便可直接返回答案，这个解法在时间复杂度上应该能够让人高山仰止了。

【解法五】查表法

代码清单2-5

/* 预定义的结果表 */

int countTable[256] =

{

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3,

3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3,

4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,

3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3,

4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6,

6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4,

5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3,

4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4,

4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6,

7, 6, 7, 7, 8

};

int Count(int v)

{

//check parameter

return countTable[v];

}

这是个典型的空间换时间的算法，把0~255中“1”的个数直接存储在数组中，v作为数组的下标，countTable[v]就是v中“1”的个数。算法的时间复杂度仅为O（1）。

在一个需要频繁使用这个算法的应用中，通过“空间换时间”来获取高的时间效率是一个常用的方法，具体的算法还应针对不同应用进行优化。

扩展问题

1. 如果变量是32位的DWORD，你会使用上述的哪一个算法，或者改进哪一个算法？

2. 另一个相关的问题，给定两个正整数（二进制形式表示）A和B，问把A变为B需要改变多少位（bit）？也就是说，整数A和B 的二进制表示中有多少位是不同的？

摘自：http://www.msra.cn/Articles/ArticleItem.aspx?Guid=edb3a02b-6d5e-42c7-b2a5-4ae4a18f4254#.

/************************* 第二篇 **********************/

算法-求二进制数中1的个数

问题描述

任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4

这也是一道比较经典的题目了，相信不少人面试的时候可能遇到过这道题吧，下面介绍了几种方法来实现这道题，相信很多人可能见过下面的算法，但我相信很少有人见到本文中所有的算法。如果您上头上有更好的算法，或者本文没有提到的算法，请不要吝惜您的代码，分享的时候，也是学习和交流的时候。

普通法

我总是习惯叫普通法，因为我实在找不到一个合适的名字来描述它，其实就是最简单的方法，有点程序基础的人都能想得到，那就是移位+计数，很简单，不多说了，直接上代码，这种方法的运算次数与输入n最高位1的位置有关，最多循环32次。

int BitCount(unsigned int n)
{unsigned int c = 0 ; // 计数器while (n > 0){if((n & 1) == 1) // 当前位是1++c ; // 计数器加1n >>= 1 ; // 移位}return c ;
}

一个更精简的版本如下

int BitCount1(unsigned int n)
{unsigned int c = 0 ; // 计数器for (c = 0; n; n >>= 1) // 循环移位c += n & 1 ; // 如果当前位是1，则计数器加1return c ;
}

快速法

这种方法速度比较快，其运算次数与输入n的大小无关，只与n中1的个数有关。如果n的二进制表示中有k个1，那么这个方法只需要循环k次即可。其原理是不断清除n的二进制表示中最右边的1，同时累加计数器，直至n为0，代码如下

int BitCount2(unsigned int n)
{unsigned int c = 0 ;for (c = 0; n; ++c){n &= (n - 1) ; // 清除最低位的1}return c ;
}

为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n – 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。

查表法

动态建表

由于表示在程序运行时动态创建的，所以速度上肯定会慢一些，把这个版本放在这里，有两个原因

1. 介绍填表的方法，因为这个方法的确很巧妙。

2. 类型转换，这里不能使用传统的强制转换，而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。

int BitCount3(unsigned int n) 
{ // 建表unsigned char BitsSetTable256[256] = {0} ; // 初始化表 for (int i = 0; i < 256; i++) { BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2]; } unsigned int c = 0 ; // 查表unsigned char * p = (unsigned char *) &n ; c = BitsSetTable256[p[0]] +  BitsSetTable256[p[1]] +  BitsSetTable256[p[2]] +  BitsSetTable256[p[3]]; return c ; 
}

先说一下填表的原理，根据奇偶性来分析，对于任意一个正整数n

1.如果它是偶数，那么n的二进制中1的个数与n/2中1的个数是相同的，比如4和2的二进制中都有一个1，6和3的二进制中都有两个1。为啥？因为n是由n/2左移一位而来，而移位并不会增加1的个数。

2.如果n是奇数，那么n的二进制中1的个数是n/2中1的个数+1，比如7的二进制中有三个1，7/2 = 3的二进制中有两个1。为啥？因为当n是奇数时，n相当于n/2左移一位再加1。

再说一下查表的原理

对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8 = 256种01组合方式，这也是为什么表的大小为256的原因。

注意类型转换的时候，先取到n的地址，然后转换为unsigned char*，这样一个unsigned int（4 bytes）对应四个unsigned char（1 bytes），分别取出来计算即可。举个例子吧，以87654321（十六进制）为例，先写成二进制形式-8bit一组，共四组，以不同颜色区分，这四组中1的个数分别为4，4，3，2，所以一共是13个1，如下面所示。

10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13

静态表-4bit

原理和8-bit表相同，详见8-bit表的解释

int BitCount4(unsigned int n)
{unsigned int table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4} ;unsigned int count = 0 ;while (n){count += table[n & 0xf] ;n >>= 4 ;}return count ;
}

静态表-8bit

首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位，并与0xff相与，取得最低位的8bit，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数2882400018为例，其对应的二进制数为10101011110011011110111100010010，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。

第一次（n & 0xff） 10101011110011011110111100010010

第二次（(n >> 8) & 0xff） 00000000101010111100110111101111

第三次（(n >> 16) & 0xff）00000000000000001010101111001101

第四次（(n >> 24) & 0xff）00000000000000000000000010101011

int BitCount7(unsigned int n)
{    unsigned int table[256] =     {        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,       1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,    };    return table[n & 0xff] +table[(n >> 8) & 0xff] +table[(n >> 16) & 0xff] +table[(n >> 24) & 0xff] ;
}

当然也可以搞一个16bit的表，或者更极端一点32bit的表，速度将会更快。

平行算法

网上都这么叫，我也这么叫吧，不过话说回来，的确有平行的意味在里面，先看代码，稍后解释

int BitCount4(unsigned int n) 
{ n = (n & 0x55555555) + ((n >> 1) & 0x55555555) ; n = (n & 0x33333333) + ((n >> 2) & 0x33333333) ; n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f) ; n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff) ; n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff) ; return n ; 
}

速度不一定最快，但是想法绝对巧妙。说一下其中奥妙，其实很简单，先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

以217（11011001）为例，有图有真相，下面的图足以说明一切了。217的二进制表示中有5个1

完美法

int BitCount5(unsigned int n) 
{unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

最喜欢这个，代码太简洁啦，只是有个取模运算，可能速度上慢一些。区区两行代码，就能计算出1的个数，到底有何奥妙呢？为了解释的清楚一点，我尽量多说几句。

第一行代码的作用

先说明一点，以0开头的是8进制数，以0x开头的是十六进制数，上面代码中使用了三个8进制数。

将n的二进制表示写出来，然后每3bit分成一组，求出每一组中1的个数，再表示成二进制的形式。比如n = 50，其二进制表示为110010，分组后是110和010，这两组中1的个数本别是2和3。2对应010，3对应011，所以第一行代码结束后，tmp = 010011，具体是怎么实现的呢？由于每组3bit，所以这3bit对应的十进制数都能表示为2^2 * a + 2^1 * b + c的形式，也就是4a + 2b + c的形式，这里a,b,c的值为0或1，如果为0表示对应的二进制位上是0，如果为1表示对应的二进制位上是1，所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子，十进制数6（0110）= 4 * 1 + 2 * 1 + 0，这里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二进制表示中有两个1。现在的问题是，如何得到a + b + c呢？注意位运算中，右移一位相当于除2，就利用这个性质！

4a + 2b + c 右移一位等于2a + b

4a + 2b + c 右移量位等于a

然后做减法

4a + 2b + c –(2a + b) – a = a + b + c，这就是第一行代码所作的事，明白了吧。

第二行代码的作用

在第一行的基础上，将tmp中相邻的两组中1的个数累加，由于累加到过程中有些组被重复加了一次，所以要舍弃这些多加的部分，这就是&030707070707的作用，又由于最终结果可能大于63，所以要取模。

需要注意的是，经过第一行代码后，从右侧起，每相邻的3bit只有四种可能，即000, 001, 010, 011，为啥呢？因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题，因为3 + 3 = 6，不足8，不会产生进位。

tmp + (tmp >> 3)-这句就是是相邻组相加，注意会产生重复相加的部分，比如tmp = 659 = 001 010 010 011时，tmp >> 3 = 000 001 010 010，相加得

001 010 010 011

000 001 010 010

———————

001 011 100 101

001 + 101 = 1 + 5 = 6，所以659的二进制表示中有6个1

注意我们想要的只是第二组和最后一组（绿色部分），而第一组和第三组（红色部分）属于重复相加的部分，要消除掉，这就是&030707070707所完成的任务（每隔三位删除三位），最后为什么还要%63呢？因为上面相当于每次计算相连的6bit中1的个数，最多是111111 = 77（八进制）= 63（十进制），所以最后要对63取模。

位标志法

感谢网友 gussing提供

struct _byte  
{  unsigned a:1;  unsigned b:1;  unsigned c:1;  unsigned d:1;  unsigned e:1;  unsigned f:1;  unsigned g:1;  unsigned h:1;  
};  long get_bit_count( unsigned char b )  
{struct _byte *by = (struct _byte*)&b;  return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h);  
}

指令法

感谢网友 Milo Yip提供

使用微软提供的指令，首先要确保你的CPU支持SSE4指令，用Everest和CPU-Z可以查看是否支持。

unsigned int n = 127 ;
unsigned int bitCount = _mm_popcnt_u32(n) ;

References

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

作者：zdd

出处：http://www.cnblogs.com/graphics/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.

/************************** 第三篇 ***********************/

问题：给出一个整数，请设计算法计算该整数以二进制格式表示时的1的个数。例如，十进制整数150，二进制表示为10010110，则1的个数为4个。要求算法效率尽可能的高。

这是今天从一个blog 上看到的题目，乍一看到题目我没想到什么思路（显然，逐个bit位的数肯定不是最优算法）。Blog上给出了算法思路和示例，读后外加实践验证后才理解了其中的这个算法（另两个高级算法实在琢磨不清楚，还请高人看到后教我）：

const UINT32 m1  = 0x55555555;  // 01010101010101010101010101010101const UINT32 m2  = 0x33333333;  // 00110011001100110011001100110011const UINT32 m4  = 0x0f0f0f0f;  // 00001111000011110000111100001111const UINT32 m8  = 0x00ff00ff;  // 00000000111111110000000011111111const UINT32 m16 = 0x0000ffff;  // 00000000000000001111111111111111/* This is a naive implementation, shown for comparison, and to help in* understanding the better functions. It uses 20 arithmetic operations* (shift, add, and).*原来这还仅仅是一个比较“天真幼稚”的实现，用来使得读者更好的理解和比较其他的更高级的*算法。*这个实现使用了20个算术操作符（包括移位、加号以及与操作）。--Adreaman*/int popcount_1(UINT32 x){x = (x & m1) + ((x >> 1) & m1); /*第一步*/x = (x & m2) + ((x >> 2) & m2); /*第二步*/x = (x & m4) + ((x >> 4) & m4); /*第三步*/x = (x & m8) + ((x >> 8) & m8);x = (x & m16) + ((x >> 16) & m16);return x;}

这个算法的设计思路是这样的（上面的例子是针对占位32bit的整数来举例的）：

设原整数值为x，

第一步：把x的32个bit分成16组（第32bit和第31bit一组，第30bit和第29bit一组……以此类推），然后将每一组的两bit 上的值（因为是二进制数，所以要么是0要么是1）相加并把结果还放在这两bit的位置上，这样，得到结果整数x1，x1的二进制（32bit）可以分为 16组，每一组的数值就是原来整数x在那两bit上1的个数。

第二步：把第一步得到的结果x1的32bit，分成8组(第32、31、30、29bit一组，第28、27、26、25bit一组……以此类推)，然后每一组的四bit上的值相加并把结果还放在这四bit的位置上，这样，又得到结果整数x2，x2的二进制可以分为8组，每一组的数值就是原来整数x在那四bit上的1的个数。

……

这样一直分组计算下去，最终，把两个16bit上1的个数相加，得到原来整数x的32bit上1的个数。

下面是我刚看这个算法时想要验证一下，写的验证程序，验证宽2bit、4bit、8bit、16bit和32bit的情况下，此算法的正确性。结果当然是没有问题啦。

注意，逐个计算32bit的计算量太大，一般的机器大概需要1天左右才能把所有32bit的整数验证完毕。

/* ============================================
* Problem:
*   The fastest way to count how many 1s in a 32-bits integer.
*
* Algorithm:
*   The problem equals to calculate the Hamming weight of a 32-bits integer,
*   or the Hamming distance between a 32-bits integer and 0. In binary cases,
*   it is also called the population count, or popcount.[1]
*
*   The best solution known are based on adding counts in a tree pattern
*   (divide and conquer). Due to space limit, here is an example for a
*   8-bits binary number A=01101100:[1]
* | Expression            | Binary   | Decimal | Comment                    |
* | A                     | 01101100 |         | the original number        |
* | B = A & 01010101      | 01000100 | 1,0,1,0 | every other bit from A     |
* | C = (A>>1) & 01010101 | 00010100 | 0,1,1,0 | remaining bits from A      |
* | D = B + C             | 01011000 | 1,1,2,0 | # of 1s in each 2-bit of A |
* | E = D & 00110011      | 00010000 | 1,0     | every other count from D   |
* | F = (D>>2) & 00110011 | 00010010 | 1,2     | remaining counts from D    |
* | G = E + F             | 00100010 | 2,2     | # of 1s in each 4-bit of A |
* | H = G & 00001111      | 00000010 | 2       | every other count from G   |
* | I = (G>>4) & 00001111 | 00000010 | 2       | remaining counts from G    |
* | J = H + I             | 00000100 | 4       | No. of 1s in A             |
* Hence A have 4 1s.
*
* [1] http://en.wikipedia.org/wiki/Hamming_weight
*
* =============================================
*/
#include

typedef unsigned int UINT32;

const UINT32 c2m1 = 0×1; // 01

const UINT32 c4m1 = 0×5; //0101
const UINT32 c4m2 = 0×3; //0011

const UINT32 c8m1 = 0×55; //01010101
const UINT32 c8m2 = 0×33; //00110011
const UINT32 c8m4 = 0×0f; //00001111

const UINT32 c16m1 = 0×5555; //0101010101010101
const UINT32 c16m2 = 0×3333; //0011001100110011
const UINT32 c16m4 = 0×0f0f; //0000111100001111
const UINT32 c16m8 = 0×00ff; //0000000011111111

const UINT32 c32m1 = 0×55555555; // 01010101010101010101010101010101
const UINT32 c32m2 = 0×33333333; // 00110011001100110011001100110011
const UINT32 c32m4 = 0×0f0f0f0f; // 00001111000011110000111100001111
const UINT32 c32m8 = 0×00ff00ff; // 00000000111111110000000011111111
const UINT32 c32m16 = 0×0000ffff; // 00000000000000001111111111111111
/*
const UINT32 c64m1 = 0×5555555555555555; //
const UINT32 c64m2 = 0×3333333333333333; //
const UINT32 c64m4 = 0×0f0f0f0f0f0f0f0f; //
const UINT32 c64m8 = 0×00ff00ff00ff00ff; //
const UINT32 c64m16 = 0×0000ffff0000ffff; //
const UINT32 c64m32 = 0×00000000ffffffff; //
*/
int popcount_2(UINT32 x)
{
x = (x & c2m1) + ((x>>1) & c2m1);
return (int)x;
}

int popcount_4(UINT32 x)
{
x = (x & c4m1) + ((x>>1) & c4m1);
x = (x & c4m2) + ((x>>2) & c4m2);
return (int)x;
}

int popcount_8(UINT32 x)
{
x = (x & c8m1) + ((x>>1) & c8m1);
x = (x & c8m2) + ((x>>2) & c8m2);
x = (x & c8m4) + ((x>>4) & c8m4);
return (int)x;
}

int popcount_16(UINT32 x)
{
x = (x & c16m1) + ((x>>1) & c16m1);
x = (x & c16m2) + ((x>>2) & c16m2);
x = (x & c16m4) + ((x>>4) & c16m4);
x = (x & c16m8) + ((x>>8) & c16m8);
return (int)x;
}

int popcount_32(UINT32 x)
{
x = (x & c32m1) + ((x >> 1) & c32m1);
x = (x & c32m2) + ((x >> 2) & c32m2);
x = (x & c32m4) + ((x >> 4) & c32m4);
x = (x & c32m8) + ((x >> 8) & c32m8);
x = (x & c32m16) + ((x >> 16) & c32m16);
return (int)x;
}
/*
int popcount_64(UINT32 x)
{
x = (x & c64m1) + ((x >> 1) & c64m1);
x = (x & c64m2) + ((x >> 2) & c64m2);
x = (x & c64m4) + ((x >> 4) & c64m4);
x = (x & c64m8) + ((x >> 8) & c64m8);
x = (x & c64m16) + ((x >> 16) & c64m16);
x = (x & c64m32) + ((x >> 32) & c64m32);
return (int)x;
}*/

/*笨算法，呵呵，但是肯定正确，用来验证比较*/

int my(UINT32 x)
{
int nCount = 0;
int i = 1;
for(i = 1; i != 0×80000000 ; i=i<<1)
{
//printf(”0x%x”,i);
if(x&i)
nCount++;
}
return nCount;
}

int main()
{
UINT32 intx= 0;
printf(”start!\n”);

printf(”List for 2 bit number:\n”);
for(intx = 0; intx!=0×3; intx++)
{
if(my(intx) != (int)popcount_2(intx))
{
printf(”No.%d : real count %d; popcount_2 = %d\n”,intx,my(intx),popcount_2(intx));
}
}

printf(”List for 4 bit number:\n”);
for(intx = 0; intx!=0xf; intx++)
{
if(my(intx) != (int)popcount_4(intx))
{
printf(”No.%d : real count %d; popcount_4 = %d\n”,intx,my(intx),popcount_4(intx));
}
}

printf(”List for 8 bit number:\n”);
for(intx = 0; intx!=0xff; intx++)
{
if(my(intx) == (int)popcount_8(intx))
{
printf(”No.%d : real count %d; popcount_8 = %d\n”,intx,my(intx),popcount_8(intx));
}
}

printf(”List for 16 bit number:\n”);
for(intx = 0; intx!=0xffff; intx++)
{
if(my(intx) != (int)popcount_16(intx))
{
printf(”No.%d : real count %d; popcount_16 = %d\n”,intx,my(intx),popcount_16(intx));
}
}

printf(”List for 32 bit number:\n”);
for(intx = 0; intx!=0xffffffff; intx++)
{
if(my(intx) != (int)popcount_32(intx))
{
printf(”No.%d : real count %d; popcount_32 = %d\n”,intx,my(intx),popcount_32(intx));
}
}

printf(”finish!\n”);
return 0;
}

第三篇摘自：http://tech.e800.com.cn/articles/2009/526/1243306374080_1.html

是不是大长见识呢？其实对于我们电工的同学来说，与我们最接近的应该是那个调用SSE4指令集的算法，够邪恶的~

查看全文
如若内容造成侵权/违法违规/事实不符，请联系编程学习网邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！

JavaScript利用计时器实现进度条(练习)
<!DOCTYPE html> <html><head><meta charset="UTF-8"><title></title><script type="text/javascript">var intervalId;var count = 0;var widthNum = 0;οnlοad=function () {var twoDiv = document.getEleme…...
2024/4/12 4:06:40
Eclipse主题插件之Darkest Dark Theme with DevStyle
今天给Eclipse换了个装、安装了新的主题插件 Darkest Dark Theme with DevStyle ，有种焕然一新的感觉、闲话少说，直接上图~~~DevStyle Theme...
2024/5/4 6:24:04
php变量和基本语法
1、PHP的基本语法PHP可以和html混编一个语法以分号结束定义变量要以$打头变量的数据类型不是不变的弱数据类型语言区分大小写 2、PHP基本数据类型：整形，浮点数，字符串，布尔型？？如果在程序中只是声明了变量，并没有直接赋值，那么在内存中该变量的值是null整形在PHP中一个…...
2024/4/12 12:43:14
nodejs 终端打印进度条
1. 场景导入当我们对大量文件进行批量处理的时候(例如：上传/下载、保存、编译等)，常常希望知道当前进展如何，或者失败(成功)的任务有多少；当我们的代码或程序已经发布，用户在执行安装的过程中，一个合适的（终端/命令行）进度条可以准确反映安装的步骤和进程，提升程序的…...
2024/4/12 9:03:16
friends101. The One Where Monica Gets a New Roommate (The Pilot)
the pilot: 美国电视剧新剧开播都会有一个试播来测试观众对新剧的接受程度，以此来决定是否再继续播下去，也可以说是一个开端，第一集，试播 [Scene: Central Park, Chandler, Joey, Phoebe, and Monica are there.]Central Park: 中央公园，坐落于纽约曼哈顿市中心 -Monica: …...
2024/4/12 4:06:40
（图解）windows下自定义Eclipse主题
之前用过一些编辑器如SublimeText，IDE如phpstorm，IDEA等；这些工具给我的感觉就是，除了给予这些工具应有的功能外，给予开发者更友好，更舒服的界面。Eclipse很早就开始使用了，之前在使用时，对它自带的经典界面倒没什么特殊的感觉，因为同期在使用的VS也差不多那个样子，后…...
2024/4/16 21:07:10
Eclipse 更换主题
主题官网： Eclipse 主题之官网下载（http://www.eclipsecolorthemes.org），如下图：下载EPF插件插件下载完成后，将主题文件 .epf 文件放到指定的文件夹中，不可再改变，如果改变了路径，则需要重新导入。打开 Eclipse 工具，在左上角工具栏，点击 ” File -> Import ”…...
2024/4/12 9:12:29
Qt学习之多线程程序设计
QT通过三种形式提供了对线程的支持。它们分别是，一、平台无关的线程类二、线程安全的事件投递三、跨线程的信号-槽连接。这使得开发轻巧的多线程Qt程序更为容易，并能充分利用多处理器机器的优势。多线程编程也是一个有用的模式，它用于解决执行较长时间的操作而不至于用户…...
2024/5/4 0:22:07
eclipse主题替换、还原
主题下载： http://eclipsecolorthemes.org/ 导入方法： myeclipse->File->Import->General->Preferencesbrowse你下载的epf路径，直接finish就可以了。还原主题方法：工作空间目录下，替换workspace\.metadata\.plugins \org.eclipse.core.runtime\.setting文件夹…...
2024/4/19 20:49:58
前端实现进度条超过文字，进度条变成相反的颜色代码
功能代码如下，经过测试没有问题： <html><head><title>前端实现进度条超过文字，进度条变成相反的颜色代码</title></head><style>*{margin:0;padding:0;}.wrap{position: relative;width:200px;height:40px;line-height:40px;margin:40p…...
2024/4/12 4:08:04
数据类型及转换
数据类型转换布尔型布尔型是PHP中较常用的数据类型之一，通常用于逻辑判断 true falsh表示事物的“真”和“假”，并且不区分大小写。整形整形可以由十进制、八进制和十六进制数指定，用来表示整数在它前面加上“-”符号，可以表示负数。八进制数使用0-7表示，且数字前必…...
2024/4/12 4:07:28
jsp+javascript进度条显示源码
游览器中打开status.jsp 文件start.jsp--------<% session.removeAttribute("task");%>//为了使每次开始都新建一个bean对象<jsp:useBean id = "task" scope = "session" class = "test.barBean.TaskBean"/><%task.set…...
2024/4/12 4:07:46
QT 关于多线程的UI界面
QT 关于多线程的动画特效先展示效果点击不同的暂停按钮会将当前的线程进入等待，然后其他两个线程会加快自己当前现成的运行速度，点开始会重新执行当前的线程。（但是这个内容中有个问题，自己懒没有修复，就是当点击了某一个暂停按钮后，不能再继续点击）下面展示一下代码…...
2024/4/19 17:21:34
DIY-eclipse主题方法---Color IDE Pack订制你自己的风格
如果你用的是eclipse而不是MyEclipse软件，那么下面教程将指引你DIY你自己的编程环境，使你增添使用eclipse编程的乐趣！好了，现在开始！第一步：在eclipse菜单栏的help选项下点击“Eclipse Marketplace”。稍等一会儿，你就会看到如下的界面：第二步：在当前的界面的“Find”…...
2024/4/12 13:16:48
MD5中使用16进制
MD5中使用16进制消息摘要分类： java_secruity2012-12-28 13:11 719人阅读评论(0) 收藏举报消息摘要由于数据在计算机中的表示，最终以二进制的形式存在，所以有时候使用二进制，可以更直观地解决问题。但，二进制数太长了。比如int 类型占用4个字节，32位。比如100，用int…...
2024/4/18 3:55:09
利用js简单实现进度条功能，替换jquery progressbar
前一段时间，要实现一个进度条的需求，但我发现项目里面用的是JQuery 1.7.3 ，而且这个页面里面已经用到了tab的JQuery UI,而且jquery引用的UI 是分好多个部分的（需要用到哪个，用哪个），但是就是没有JQuery UI-progressbar，而且我从网上找了好久，还是没有找到1,7,3,的JQue…...
2024/4/12 4:07:52
COM：追踪植物-微生物组互作的进化历史
追踪植物-微生物组互作的进化路径 Tracing the evolutionary routes of plant–microbiota interactions Current Opinion in Microbiology [6.916] 2019-11-4，Review 原文链接： https://doi.org/10.1016/j.mib.2019.09.013 第一作者：Carmen Escudero-Martinez 通讯作者：Da…...
2024/4/12 4:07:34
Python3入门与进阶【笔记】
1、二、八、十六进制转十进制：int(10, base=2)、int(10, base=8)、int(10, base=16)； 2、八、十、十六进制转二进制：bin(0o+xxx)、bin(xxx)、bin(0x+xxx)； 3、二、十、十六进制转八进制：oct(0b+xxx)、oct(xxx)、oct(0x+xxx)； 4、二、八、十进制转十六进制：hex(ob+xxx)、…...
2024/4/12 4:08:10
Eclipse主题下载安装
http://www.eclipsecolorthemes.org/访问eclipse主题下载网站选择喜欢的主题样式下载导入eclipse...
2024/4/12 4:07:40
QT 主进程多线程UI问题
QT 主进程多线程UI问题 1.简介由于在主线程以及多线程中对GUI进行绘画刷新，导致了出现莫名其妙的问题。例如： 1、在程序运行了一段时间后，程序UI不会刷新，运行的获取当前程序时间的程序一直在运行，但是不会将当前时间显示到界面上，其他后台显示信息，一切正常。经过鼠标…...
2024/4/19 22:56:31

计算某正整数换算成二进制后bit为1的个数

算是上一篇的续集

[算法]计算某正整数换算成二进制后bit为1的个数

扩展问题

算法-求二进制数中1的个数

问题描述

普通法

快速法

查表法

动态建表

静态表-4bit

静态表-8bit

平行算法

完美法

位标志法

指令法

相关文章

最新文章