0001 #define POW(c) (1 << (c)) //2^c
0002 #define MASK(c) (((unsigned long) -1) / (POW(POW(c)) + 1)) //以2^c位为单位分组，相间地全0和全1
0003 // MASK(0) = 55555555(h) = 01010101010101010101010101010101(b)
0004 // MASK(1) = 33333333(h) = 00110011001100110011001100110011(b)
0005 // MASK(2) = 0f0f0f0f(h) = 00001111000011110000111100001111(b)
0006 // MASK(3) = 00ff00ff(h) = 00000000111111110000000011111111(b)
0007 // MASK(4) = 0000ffff(h) = 00000000000000001111111111111111(b)
0008 
0009 //输入：n的二进制展开中，以2^c位为单位分组，各组数值已经分别等于原先这2^c位中1的数目
0010 #define ROUND(n, c) (((n) & MASK(c)) + ((n) >> POW(c) & MASK(c))) //运算优先级：先右移，再位与
0011 //过程：以2^c位为单位分组，相邻的组两两捉对累加，累加值用原2^(c + 1)位就地记录
0012 //输出：n的二进制展开中，以2^(c + 1)位为单位分组，各组数值已经分别等于原先这2^(c + 1)位中1的数目
0013 
0014 int countOnes2 ( unsigned int n ) { //统计整数n的二进制展开中数位1的总数
0015    n = ROUND ( n, 0 ); //以02位为单位分组，各组内前01位与后01位累加，得到原先这02位中1的数目
0016    n = ROUND ( n, 1 ); //以04位为单位分组，各组内前02位与后02位累加，得到原先这04位中1的数目
0017    n = ROUND ( n, 2 ); //以08位为单位分组，各组内前04位与后04位累加，得到原先这08位中1的数目
0018    n = ROUND ( n, 3 ); //以16位为单位分组，各组内前08位与后08位累加，得到原先这16位中1的数目
0019    n = ROUND ( n, 4 ); //以32位为单位分组，各组内前16位与后16位累加，得到原先这32位中1的数目
0020    return n; //返回统计结果
0021 } //32位字长时，O(log_2(32)) = O(5) = O(1)