Leetcode——191.位1个数——5种题解+代码实现

一、题目


编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

 

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

 

提示:

  • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
  • 在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3

 

进阶:
如果多次调用这个函数,你将如何优化你的算法?


二、题解思路


  • 方法一题解思路:使用bitset操作,先使用bitset将无符号整数转换成32位二进制数,然后使用bitset中的count操作,计算出二进制中1的个数。
  • 方法二题解思路:使用求余、整除操作,结合while循环。
  • 方法三题解思路:使用与操作和右移操作。提示:能使用移位操作,就尽量不使用除法操作,此种方法遇到负数会出现死循环,一直右移会出现0xFFFFFFFF。
  • 方法四题解思路:为了避免死循环,将针对n的二进制上的每一位进行单独判断,第一次循环让n与1按位与,判断最右边倒数第一个是否为1,第二次循环让n与2按位与,判断最右边倒数第二个是否为1,第三次循环让n与4按位与,判断最右边倒数第三个是否为1........
  • 方法五题解思路:把一个整数减去1,然后将结果和原来的整数做按位与操作,就会把原来整数二进制最右边的1变成0,这样一个二进制中有多少个1,就做多次。

三、代码实现


  • 方法一C++代码实现
class Solution {
public:
    int hammingWeight(uint32_t n) 
    {
        bitset<32> nums(n);
        return nums.count();   //bitset中的函数count:返回二进制中标志位1出现的次数
    }
};
  • 方法二C++代码实现
class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int counts = 0;
        while(n)
        {
            if(n%2 == 1)
                counts++;
            n /= 2;
        }
        return counts;
    }
};
  • 方法三C++代码实现
class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int counts = 0;
        while(n)
        {
            if(n&1)//对于n求余,余数是1,则可以使用此种操作来判断,n与1做按位与操作,若余数是1则此操作返回的是真即1,反之则反
                counts++;
            n = n>>1;   //右移一位操作,相当于除以2,能使用移位操作别使用除法操作
        }
        return counts;
    }
};
  • 方法四C++代码实现
class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int counts = 0;
        unsigned int flag = 1;
        while(flag)
        {
            if(n&flag)   //n的当前二进制位是1
                counts++;
            flag = flag << 1; //1、2、4、6、8.......
        }
        return counts;
    }
};
  • 方法五C++代码实现
class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int counts = 0;
        while(n)
        {
            counts++;
            n = (n-1)&n;
        }
        return counts;
    }
};

 

;