统计整数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;
}

Or

int 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;
}

最后

以上就是喜悦酸奶为你收集整理的统计整数n的二进制表示中1的个数的全部内容，希望文章能够帮你解决统计整数n的二进制表示中1的个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。