计算二进制整数中bit位1的个数问题

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

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

const UINT32 m1  = 0x55555555;  // 01010101010101010101010101010101
const UINT32 m2  = 0x33333333;  // 00110011001100110011001100110011
const UINT32 m4  = 0x0f0f0f0f;  // 00001111000011110000111100001111
const UINT32 m8  = 0x00ff00ff;  // 00000000111111110000000011111111
const 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]
*
* =============================================
*/
#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;
}

原文地址：