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

时间:2022-01-22 20:56:29

(1).逐位判断(位运算)

Int get_counte(int 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 get_counter(int n)

{

         Int counter = 0;

         While (n) {

                   Counter++;

                   N &= (n-1);

}

Return counter;

}

(3)查表法

32位(64位)整型数分切割成n个区间,每个区间位长位8。分别统计每个位区间中1个个数,然后相加。

Const int index[256] = {0, 1, 1, ..., 8}; 0255中每个数包含1个个数

Int get_counte(int n)

{

         Int counter = 0;

         For (; n > 0; n >> 8) {

                   Counter += idx[n&255];

}

Return counter;

}

Or

 Int get_counter(int x)

{

         Char *p = (char *)&x;

         Return idx[*p] + idx[*(p+1)] + idx[*(p+2)] + idx[*(p+3)]

}

4.归并法。

         对于一个32位整数,先分成16组,每组2位,统计其中1个数,然后将统计的结果两两合并,得到8组,然后再此基础上,合并得到421,最总得到结果。

Int get_counter(int n)

{

         N = (n & 0x55555555) + ((n >> 1) &0x55555555);

         N = (n & 0x33333333) + ((n >> 2) &0x55555555)

         N = (n & 0x0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);

         N = (n & 0x00ff00ff) + ((n >> 8)) & 0x00ff00ff;

         Return n;

}