leetcode191-位1的个数

题目

这是一道easy难度的题，先看看题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

解答

当然在JavaScript中，也是没有无符号整数类型的，都是32位有符号整数类型。所以这里我们的输入都是有符号整数类型。那么我们的问题就转换成了输入一个整数，返回其二进制表达式中数字位数为‘1’的个数

十进制转二进制

这里我们很容易想到，将数字处理成二进制，然后统计其1的个数。从十进制转成二进制，不断除以2，直到为0。

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    while (n) {
        count += n % 2; 
        n = n >> 1;
        // n = Math.floor(n / 2);
    }
    return count;
};

位运算

循环和位移动

将输入的数字n与位掩码(初始值为1)的二进制做与运算，即可以得到n的最低位。举个例子

已知 0 & 1 = 0, 1 & 1 = 1

1的二进制表示是0000 0000 0000 0000 0000 0000 0000 0001
3的二进制表示是0000 0000 0000 0000 0000 0000 0000 0011

则 1 & 3，
结果二进制表示是0000 0000 0000 0000 0000 0000 0000 0001，即为1,得到了3的最低位。

检查下一位时，我们将掩码左移一位。

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let counts = 0;
    let mask = 1;
    for (let i = 0; i < 32; i++) {
        if ((n & mask) !== 0) {
            counts++;
        }
        mask <<= 1;
    }
    return counts;
};

位运算更简洁的做法

前面一种算法，需要检查数组的每一位。接下来的这种做法，不需要检查完每一位。而是通过不断的把数字的最后一个1进行反转。

核心思想是想法是对于任意数字 n ，将 n 和 n - 1 做与运算，会把最后一个 1 的位变成 0

1
2
3

n           ...1110100 // 倒数第3位是1
n - 1       ...1110011
n & (n -1)  ...1110000 // 倒数第3位为0

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let counts = 0;
    while(n) {
        counts++;
        n &= n - 1
    }
    return counts;
};

leetcode链接

https://leetcode-cn.com/problems/number-of-1-bits/