【每日一道LeetCode】——191. 位1的个数

作者简介：一名大一在校生 

个人主页：月亮嚼成星~

个人WeChat：yx1552029968

系列专栏：每日一道LeetCode

每日一句： 决定一个人成就的，不是靠天，也不是靠运气，而是坚持和付出，是不停地做，重复的做，用心去做，当你真的努力了付出了，你会发现自己潜力无限！ 

目录

原题：位1的个数

解题思路：

总结：

---

原题：位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：这道题涉及到了二进制位运算和移位运算的知识，不知道的铁汁们可以看一下博主的这一篇文章，浅浅的介绍了相关知识，帮助我们来做题：【Java SE]位运算和移位运算注意事项 

解题思路：

方法一：暴力移位求解

为了记录1的位数，我们需要设置一个计数器count并将其初始化为0；为了得出一个位置是否为1，要用按位与（&）1来进行操作，如果是1，结果就是1，不是1，结果为0。这只是一个位置的比较，考虑到有32位，所以我们运用位运算来实现每一位与1进行比较，循环后即可得到1的数。 为了便于理解，画了个第一次比较的图，后面的比较方法一样。

这道题当然会有更多优秀的解法，随着思路的开阔，我们将会想到更多好的解法！ 

代码执行： 

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count=0;//计数器
        for(int i=31;i>=0;i--){
            if(((n>>i)&1)==1){
                count++;
            }
        }
        return count;
        
    }
}

• 复杂度分析：时间复杂度O(k)，k=32。空间复杂度为O(1)

执行结果：

 

方法2：优化循环的过程

思路：巧用二进制公式x&(x-1)表示去掉二进制中最右边的第一个1，加速循环过程

代码执行：

public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
}

运行结果：

 

复杂度分析：时间复杂度为O(k)，k为二进制中1的个数，最坏的情况下所有位都是1。空间复杂度是O(1)

总结：

每天都来刷一道LeetCode是多么幸福的一件事，各位，共勉！！