关于java:二进制中-1-的个数

题目链接

剑指 Offer 15. 二进制中 1 的个数

题目形容

请实现一个函数，输出一个整数，输入该数二进制示意中 1 的个数。例如，把 9 示意成二进制是 1001，有 2 位是 1。因而，如果输出 9，则该函数输入 2。

示例 1：

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

示例 2：

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

示例 3：

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

留神：本题与主站 191 题雷同：https://leetcode-cn.com/probl…

解题计划

思路 1

• 标签：位运算
• 整体思路：通过与 1 进行与运算，能够判断末位是不是 1，而后将数字进行无符号右移，最终当数字变成 0 时完结判断
• n 示意数字的位数，工夫复杂度：$O(n)$，空间复杂度：$O(1)$

算法流程 1

1. 首先注意力扣在代码模板中标注了 n 是一个无符号数，如果 n 可能是正数还须要另行探讨
2. 初始化计数器 count 为 0
3. 无符号数 n 与 1 进行与运算，如果 $n \& 1 == 1$，阐明 n 的末位为 1，则 count 加一，如果 $n \& 1 == 0$，阐明 n 的末位为 0，则 count 不变
4. 判断完末位之后，将 $n = n >>> 1$ 进行无符号右移，更新末位
5. 当 $n == 0$ 时，完结判断

代码 1

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            count += n & 1;
            n = n >>> 1;
        }
        return count;
    }
}

画解 1

<,,,,,,,,,,,,,,,>

思路 2

• 标签：位运算
• 整体思路：通过与 $n = n & (n – 1)$ 的运算间接获取最初一位为 1 的地位，缩小工夫复杂度
• n 示意数字中蕴含 1 的位数，工夫复杂度：$O(n)$，空间复杂度：$O(1)$

算法流程 2

1. 首先注意力扣在代码模板中标注了 n 是一个无符号数，如果 n 可能是正数还须要另行探讨
2. 初始化计数器 count 为 0
3. $n = n & (n – 1)$ 的运算能够间接获取到以后数字最初一位为 1 的地位，同时更新 n
4. 当 $n == 0$ 时，完结判断

代码 2

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

画解 2

<,,,,,,,>

花絮