几种求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)，但空间占用比较大，且数组的寻址开销也很大。只有在特定环境中才建议使用。

最后

以上就是俊秀小海豚为你收集整理的几种求32位数中1的个数的算法的全部内容，希望文章能够帮你解决几种求32位数中1的个数的算法所遇到的程序开发问题。

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