计算int型数据的二进制形式中——1的个数

62 阅读 0 评论 41 点赞

我是靠谱客的博主虚幻发箍，最近开发中收集的这篇文章主要介绍计算int型数据的二进制形式中——1的个数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

解法一：利用整型数据除法的特点，通过相除和判断余数的值来分析1的个数.
例如：1011 0110
第一次除以2，商为 1011 011，余为 0.
第二次除以2，商为 1011 01 ，余为 1.
对于二进制操作，对数字除以2，原来的数字就会减少一个0，如果有余数，则表明当前位置有一个1.
代码如下：

int count1_1(int num)
{
int count = 0;
while(num)//num不等于0进入循环
{
if(num%2 != 0)
{
count++;
}
num /= 2;
}
return count;
}

时间复杂度：O(n)

解法二：利用位操作，除以二相当于>>(右移)一位，再通过&操作符，逐位进行判断
&: 1&1 -> 1
0&1 -> 0
1或是0，&1都是其本身，所以利用&1对整数的每一位进行判断.
代码如下：

int count1_2(int num)
{
int count = 0;
while(num)
{
count += num&1;
num >>= 1;
}
return count;
}

时间复杂度：O(Log2n)

解法三：在位操作符&的基础上，&(num-1)
&(num-1) 相比 &1 的好处在于：直接找到最右边的1进行判断.
例如：1011 1010
第一次&(num-1)，1011 1010 & 1011 1001 -> 1011 1000
第二次&(num-1)，1011 1000 & 1011 0100 -> 1011 0000
代码如下：

int count1_3(int num)
{
int count = 0;
while(num)
{
num &= (num-1);
count++;
}
return count;
}

时间复杂度：O(M)(M为1的个数)

解法四：空间换时间，分支操作
以一字节长的数据为例，可以把0~255的情况全部列举出来。这种做法提供的思路是——采用空间换时间的方法，罗列所有情况并直接给出值。

int count1_4(int num)
{
int count = 0;
switch(num)
{
case 0x0:
count = 0;
break;
case 0x1:
case 0x2:
case 0x4:
case 0x8:
case 0x10:
case 0x20:
case 0x40:
case 0x80:
num = 1;
break;
case 0x3:
case 0x6:
case 0xc:
case 0x18:
case 0x30:
case 0x60:
case 0xc0:
num = 2;
break;
//...
}
return count;
}

时间复杂度：O(1)

解法五：空间换时间，查表法
典型的空间换时间的算法，把0~255中“1”的个数直接存储在数组中，num作为下标。
空间换时间的做法，是为了获得高的时间效率，但是应该根据实际问题来取舍。

//预定义的结果表
int countTable[256] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3//每一个元素分别代表对应数字(下标)中“1”的个数
};
int count1_5(int num)
{
return countTable[num];
}

时间复杂度：O(1)

解法五：位操作，(考虑到负数)数字进行左移操作<<，&(1<<31)
考虑到负数，进行>>操作之后，左边的符号位一直在补1，所以调整为向左移<<，再 &(1<<31)来进行逐位判断。
代码如下:

int count1_5(int num)
{
int count
= 0;
int i = 1;
i <<= 31;
while(num != 0)
{
if((num&i) != 0)
{
count++;
}
num <<= 1; //负数右移之后，左边补1，为了避免这种情况，选择从左开始移位操作
return
count;
}