计算二进制整数中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
*/
 Continue reading ...