LeetCode 191. 位1的个数

摘要：
位运算判断最低位1。

题目

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

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

示例 1：

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

示例 2：

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

示例 3：

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

提示：

输入必须是长度为 32 的二进制串。

lowbit

使用lowbit找到 x 最低位1以及其更低位所有0所表示的数，更新 x.

C++
Java

// 执行用时: 0 ms
// 内存消耗: 5.9 MB
class Solution {
public:

    inline uint32_t lowbit(uint32_t x) {return x & -x;}

    int hammingWeight(uint32_t n) {
        int res = 0;
        for (; n; n -= lowbit(n)) res++;
        return res;
    }
};

// 执行用时: 1 ms
// 内存消耗: 35.3 MB
public class Solution {
    // you need to treat n as an unsigned value
    private int lowbit(int x) {return x & -x;}

    public int hammingWeight(int n) {
        int res = 0;
        for (; n != 0; n -= lowbit(n)) res++;

        return res;
    }
}

注意c++和java的传入参数 n 一个是无符号整型（unsigned int）一个是有符号整型（int），因为java中没有无符号整型，所以理解的时候需要注意区别。但是代码没有区别，因为不管有无符号，数字在计算机底层都是以补码形式表示的， lowbit 返回的值一定是补码最低位1以及其更低位所有0表示的数。

举个例子说明它们的区别，对于示例3：
11111111111111111111111111111101
这个二进制数字在这道题的c++中表示为一个补码正数 4294967293，
而在java中，因为是有符号的，表示一个补码负数 -3.
也就是说，这道题在LeetCode后端评测器参数设定中，是用的不同数字分别表示c++和java语言中的这个二进制数的。

c++中对这个数进行一次 lowbit 操作得到的数为：
1 ，对应二进制补码为 00000000000000000000000000000001
java中对这个数进行一次 lowbit 操作得到的数为：
1 ，对应二进制补码为 00000000000000000000000000000001
是完全相同的。
lowbit 赛高~！

位运算小技巧

在二进制表示中，数字 n 的 最低位 1总是对应 n - 1 中的0。
也就是说，n - 1 恰好等于，n 的最低位1开始到最低位全部取反（因为和 n 的最低位借了一位1），最低位1开始到最高位全部不变。
利用这一性质，利用 n & n - 1 可以巧妙找到最低位1，即， n & n - 1 为最低位1开始到最低位全部为0，到最高位全部相同.
在这里, n & n - 1 等价于 n - lowbit(n).

c++
java

// 执行用时: 0 ms
// 内存消耗: 5.8 MB
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;

        for (; n; n &= n - 1) res++;

        return res;
    }
};

// 执行用时: 1 ms
// 内存消耗: 35.2 MB
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;

        for (; n != 0; n &= n - 1) res++;

        return res;
    } 
}

循环，用掩码判断

从最低位开始，设置一个掩码，初始化为 00000000000000000000000000000001.
让其对原数字进行 & 运算，判断最低位是否为 1。
然后掩码左移一位，更新掩码，依次逐位判断当前位是否为 1.
注意在c++中，需要用无符号整型来表示掩码。

c++
java

// 执行用时: 0 ms
// 内存消耗: 5.7 MB
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        uint32_t mask = 1;
        for (int i = 0; i < 32; i ++) {
            if (n & mask) res++;
            mask <<= 1;
        }
        return res;
    }
};

// 执行用时: 1 ms
// 内存消耗: 36.2 MB
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        int mask = 1;
        for (int i = 0; i < 32; i ++) {
            if ((n & mask) != 0) res++;
            mask <<= 1;
        }
        return res;
    } 
}

循环，用原数字判断

可以固定掩码 1，不断右移原数字，始终判断最低位。
因为c++中，原数字为无符号整型，所以原数字可以直接右移；
而java中，原数字有符号，所以需要使用无符号右移运算符 >>>.

c++
java

// 执行用时: 0 ms
// 内存消耗: 5.9 MB
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int mask = 1;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (n & mask) res++;
            n >>= 1;
        }
        return res;
    }
};

// 执行用时: 1 ms
// 内存消耗: 35.4 MB
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        int mask = 1;

        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) res++;
            n >>>= 1;
        }

        return res;
    }
}

轮子

使用c++和java的内置轮子。

c++
java

// 执行用时: 0 ms
// 内存消耗: 5.8 MB
class Solution {
public:
    int hammingWeight(uint32_t n) {
        return __builtin_popcount(n);
    }
};

// 执行用时: 1 ms
// 内存消耗: 35.2 MB
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

原题链接： LeetCode 191. 位1的个数