Number of 1 Bits

Q: Number of 1 Bits 的时间复杂度是多少？

移位循环会针对每个二进制位运行一次： O(log n) ，这里最多 31 步。 n & (n-1) 循环会针对每个值为 1 的位运行一次： O(k) ，其中 k 是答案。两者都只使用 O(1) 的额外空间。

Q: 有内置函数可以统计置位的位数吗？

大多数语言都有相关功能，通常由一条处理器指令实现：Java 中的 Integer.bitCount 、GCC 中的 __builtin_popcount 、Go 中的 bits.OnesCount 、Rust 中的 count_ones ，以及 Python 3.10 及更高版本中的 int.bit_count 。面试时，写出循环，并提一下内置函数。

Q: 汉明重量和汉明距离有什么区别？

一个数字的汉明重量是它的二进制位中 1 的个数，这就是本题返回的结果。两个数字之间的汉明距离是它们不同的位数：统计 a ^ b 中 1 的个数，因为 XOR 恰好会将它们不同的位置设为 1。

简单位运算

+10

给你一个非负整数 n。将 n 写成二进制，并返回其中 1 的位数。这个数量也称为置位数、人口计数或汉明重量。例如，6 的二进制表示是 110，所以它有两个值为 1 的位。

函数

hammingWeight(n: integer) → integer

ninteger: 可存储在有符号 32 位整数中的非负整数
返回值integer: n 的二进制形式中 1 的个数

约束条件

0 ≤ n ≤ 2³¹-1

示例

输入: n = 11
输出: 3
解释: 11 的二进制表示是 1011，也就是 8 + 2 + 1。它的 4 位二进制数中有 3 位是 1，所以答案是 3。

输入: n = 128
输出: 1
解释: 128 是 2^7，写作 10000000：一个 1 后面跟着若干个 0，所以答案是 1。

进阶

如果这个函数运行数百万次，你怎样用 4 次查表来统计一个 32 位数字中的位数？表中预先计算好了 256 个数值的位数。

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

无需构建字符串即可查看 n 的二进制位。读取最后一位并将其移除，每个二进制位需要一步，最多 31 步。使用 n & (n-1) 清除最低位的 1，每个 1 需要一步，步数恰好等于答案。

检查最后一位并右移

思路

n & 1 是 n 的最后一位二进制数字：n 是奇数时为 1，是偶数时为 0。把它加到计数中。然后，n >> 1 会去掉这一位，并将下一位移到最后一位；对于非负数，这相当于除以 2 后向下取整。对于 11，也就是 1011，随着 n 缩小到 0，最后几位依次是 1、1、0 和 1：共有三个 1 位。

当 n 为 0 时，循环停止，因此不会遍历前导零：大约需要 log2(n) 步，128 需要 8 步，最多 31 步。它只存储 n 和计数。

算法

将计数器设为 0。
当 n 大于 0 时，将 n & 1 加到计数器中。
将 n 右移一位。
当 n 达到 0 时，返回计数器。

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

使用 n & (n-1) 清除最低位的 1

思路

减去 1 会将最低位的 1 变成 0，并将它下面的每个 0 变成 1，而更高位保持不变。因此，n & (n-1) 会保留高位并清除最低位的 1：12 是 1100，11 是 1011，而 1100 & 1011 是 1000。

每一步都会恰好移除一个 1 位，因此将 n 变为 0 所需的步数就是答案。128 只需 1 步，而不是 8 步，不过 2^31-1 仍需 31 步。Lua 5.1 没有位运算符，因此它的版本通过不断除以 2 来找到最低位的 1，并将其减去；循环仍会对每个 1 位运行一次。

算法

将计数器设为 0。
当 n 不为 0 时，将 n 替换为 n & (n-1)。
每次替换后，将计数器加 1。
返回计数器。

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

易错点和边界情况

当 n > 1 时循环。循环会在处理最后一个 1 位之前停止，因此当 n = 1 时返回 0。
使用浮点数进行除法。在 JavaScript、Lua 和 R 中，11 / 2 的结果是 5.5，之后得到的余数也会是小数。使用 Math.floor、math.floor 或 %/% 向下取整，也可以改用移位。
在 Lua 5.1 中写 n & 1。它没有位运算符，因此代码无法编译。请改用 n % 2 和 math.floor(n / 2)。

常见问题3

Number of 1 Bits 的时间复杂度是多少？

移位循环会针对每个二进制位运行一次：O(log n)，这里最多 31 步。n & (n-1) 循环会针对每个值为 1 的位运行一次：O(k)，其中 k 是答案。两者都只使用 O(1) 的额外空间。

有内置函数可以统计置位的位数吗？

大多数语言都有相关功能，通常由一条处理器指令实现：Java 中的 Integer.bitCount、GCC 中的 __builtin_popcount、Go 中的 bits.OnesCount、Rust 中的 count_ones，以及 Python 3.10 及更高版本中的 int.bit_count。面试时，写出循环，并提一下内置函数。

汉明重量和汉明距离有什么区别？

一个数字的汉明重量是它的二进制位中 1 的个数，这就是本题返回的结果。两个数字之间的汉明距离是它们不同的位数：统计 a ^ b 中 1 的个数，因为 XOR 恰好会将它们不同的位置设为 1。

def hammingWeight(n):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

n = 11

预期输出