- daily a LeetCode 】 【 191. A number of 1

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

个人主页：月亮嚼成星~

个人WeChat：yx1552029968

系列专栏：每日一道LeetCode

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

目录

原题：位1的个数

解题思路：

总结：

---

原题：位1的个数

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：This problem involves the knowledge of binary bit operations and shift operations,Those who don't know the iron juice can look at this blogger's article,A brief introduction to the relevant knowledge,Help us do the quiz：【Java SE]位运算和移位运算注意事项 

解题思路：

方法一：Violent displacement solution

为了记录1的位数,We need to set up a countercount并将其初始化为0;In order to find out whether a position is 1,To use bitwise AND（&）1来进行操作,如果是1,结果就是1,不是1,结果为0.This is just a positional comparison,考虑到有32位,So we use bitwise operations to implement each bitwise AND1进行比较,available after the cycle1的数. 为了便于理解,Draw a picture for the first comparison,The latter comparison method is the same.

Of course there are better solutions to this problem,With an open mind,We will think of more good solutions！ 

代码执行： 

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)

总结：

Brush one every dayLeetCode是多么幸福的一件事,各位,共勉！！