191. 位1的个数

categories: [Blog,Algorithm]

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++) {
            if ((n & mask) != 0) {
                bits++;
            }
            mask <<= 1;
        }
        return bits;
//作者：LeetCode
//链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode/
    }
}

复杂度分析

时间复杂度：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/

二进制