计算二进制整数中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] http://en.wikipedia.org/wiki/Hamming_weight
*
* =============================================
*/
#include <stdio.h>

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 = 0x0f; //00001111

const UINT32 c16m1 = 0×5555; //0101010101010101
const UINT32 c16m2 = 0×3333; //0011001100110011
const UINT32 c16m4 = 0x0f0f; //0000111100001111
const UINT32 c16m8 = 0x00ff; //0000000011111111

const UINT32 c32m1? = 0×55555555;? // 01010101010101010101010101010101
const UINT32 c32m2? = 0×33333333;? // 00110011001100110011001100110011
const UINT32 c32m4? = 0x0f0f0f0f;? // 00001111000011110000111100001111
const UINT32 c32m8? = 0x00ff00ff;? // 00000000111111110000000011111111
const UINT32 c32m16 = 0x0000ffff;? // 00000000000000001111111111111111
/*
const UINT32 c64m1? = 0×5555555555555555; //
const UINT32 c64m2? = 0×3333333333333333; //
const UINT32 c64m4? = 0x0f0f0f0f0f0f0f0f; //
const UINT32 c64m8? = 0x00ff00ff00ff00ff; //
const UINT32 c64m16 = 0x0000ffff0000ffff; //
const UINT32 c64m32 = 0x00000000ffffffff; //
*/
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;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>