几种求32位数中1的个数的算法
方法一：最简单的循环位运算
int count1(int i)
{
int num=0;
while(i!=0)
{
num += i & 0x01;
i >>>= 1;
}
return num;
}
时间复杂度是O(n)，且n一定是32。
方法二：n&(n-1)
int count2(int i)
{
int num = 0;
while(i!=0) {
i &= (i-1);
num++;
}
return num;
}
时间复杂度也是O(n)，但只有在最坏情况下n才为32
方法三：查表发
查表发利用空间换取时间，利用一个32位的数组存储0~2^32的数每个数字的1的位数，利用arr[n]即可得到结果，时间复杂度为O(1)，但是空间复杂度为O(2^n)。一般情况下不会使用一个大表直接查询，而是将32位拆分成4个8位数字，分别进行4次查表操作，然后将结果相加。
int count3(int n)
{
int[] bitCount = new int[256]{0,1,1,2,1,2,...};
return bitCount[n>>>24] +
bitCount[(n&0x00ff0000) >> 16] +
bitCount[(n&0x0000ff00) >> 8] +
bitCount[(n&0x000000ff)];
}
时间复杂度为O(1)，但空间占用比较大，且数组的寻址开销也很大。只有在特定环境中才建议使用。
