统计整数n的二进制表示中1的个数

(1)逐位判断（位运算）int counter_ones(unsigned n){int counter = 0;While (n) {counter += n&1;n >>=1;}return counter;}(2)一个整型不为0，那么二进制表示时，至少包含一位1。如果整数减去1，那么最右边的1变成0，而该1后面的0变成1，其余位不变。将原来的整数和减去1后的数做与运算，从原来最右边的那个1开始所有的，所有位变成0，如：1100&（1100-1=1011）=1000。也就是说整数与该数-1后做与运算，会把最右边一个1变成0。int counter_ones(unsigned n){int counter = 0;While (n) {counter++;n &= (n-1);}return counter;}(3)查表法将32位(64位)整型数分切割成n个区间，每个区间位长位8。分别统计每个位区间中1个个数，，然后相加。static const unsigned char BitsSetTable256[256] ={# define B2(n) n, n+1, n+1, n+2# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2) B6(0), B6(1), B6(1), B6(2)};int counter_ones(unsigned n){int counter = 0;for (; n > 0; n >> 8) {counter += BitsSetTable256[n&255];}return counter;}Orint counter_ones(unsigned n){ char *p = (char *)&n; return BitsSetTable256[*p] + BitsSetTable256[*(p+1)] + BitsSetTable256[*(p+2)] + BitsSetTable256[*(p+3)]}(4)归并法。对于一个32位整数，先分成16组，每组2位，统计其中1个数，然后将统计的结果两两合并，得到8组，然后再此基础上，合并得到4，2，1，最总得到结果。int counter_ones(unsigned 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;

}

参考：~seander/bithacks.html#CountBitsSetNaive

看看花儿冲破北疆漫漫寒冬，妖娆绽放;