191. Number of 1 Bits 「位 1 的个数」

编写一个函数可以计算无符号整数中位 1 的个数(即汉明重量)。

例一:
输入: 00000000000000000000000000001011
输出: 3
解释: 输入的二进制字符串 00000000000000000000000000001011 共有 3 个位 1。

例二:
输入: 00000000000000000000000010000000
输出: 1
解释: 输入的二进制字符串 00000000000000000000000010000000 共有 1 个位 1。

例三:
输入: 11111111111111111111111111111101
输出: 31
解释: 输入的二进制字符串 11111111111111111111111111111101 共有 31 个位 1。

提示:
1. 在某些语言中,比如 Java,不存在无符号整数类型。这种情况下,给定的输入将会是有符号整数类型,但这应该对你的实现没有影响,因为有符号或无符号实际上的二进制表示形式是一样的。
2. 在 Java 中,编译器使用二进制补码来表示有符号整数。因此,在例三中的输入表示的有符号整数为 -3

二进制数中 1 的个数这个问题可以说是很常见的基础问题了。

最简单最慢的方法就是转换成字符串查 1 的数量。比较快的方法是使用位运算。

举例来说,整数 35,用二进制表示就是 0010 0011,二进制数中有 3 个 1。计算这个数字中的 1 的个数,使用与运算便可以快速完成。

这里有个位运算的小知识,n & (n-1) 可以消去二进制数的最右边的 1。比如 35 & 34

0010 0011
0010 0010
---------
0010 0010

结果得到 34,接下来 34 & 33

0010 0010
0010 0001
---------
0010 0000

结果得到 32,接下来 32 & 31

0010 0000
0001 1111
---------
0000 0000

结果得到 0,计算过程便完成了。

在得到 0 之前,一共计算了 3 次,也就是说一共消去了 3 个 1。即,给定数字 35,得出结果为 3

使用 C 语言表示以上算法:

int hammingWeight(uint32_t n) {
    if (!n)
        return 0;
    uint8_t sum;
    for (sum = 0; n; sum++) {
        n &= (n - 1);
    }
    return sum;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注