191. 位1的个数

191. 位 1 的个数

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

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) &#123;
            if ((n & mask) != 0) &#123;
                bits++;
            &#125;
            mask <<= 1;
        &#125;
        return bits;

//作者：LeetCode
//链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/
    &#125;
&#125;

复杂度分析

时间复杂度：O(1) 。运行时间依赖于数字 n 的位数。由于这题中 n 是一个 32 位数，所以运行时间是 O(1) 的。

空间复杂度：O(1)。没有使用额外空间。

---

在二进制表示中，数字 n 中最低位的 1 总是对应 n−1 中的 0 。因此，将

n 和 n−1 与运算总是能把 n 中最低位的 1 变成 0 ，并保持其他位不变。

使用这个小技巧，代码变得非常简单。

Java

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

作者：LeetCode

链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/

二进制

N	N-1	N&(N-1)
11	10	10
10	1	0
1100	1011	1000
1000	111	0
1011	1010	1010
1010	1001	1000
1000	111	0