LeetCode

191. Number of 1 Bits

文章目录
  1. 1. 题目
  2. 2. 思路

题目

思路

这道题并不难但是依然出了一点点问题…（是的一点点而已）

我一开始尝试使用map把这个东西直接给转化成一堆01的list，但是出现了bug。我刚开始以为是因为python3的map返回的是一个迭代器，但是在外面加了list之后倒是不报bug了，结果反而不对了。于是我猜问题可能是在二进制上，于是用bin函数尝试转换为二进制，最后的答案如下：

1
2
3
4
5
6
7
8
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        l = bin(n)
        return l.count('1')

还有一种暴力解法，遍历n并且记录1的个数：

1
2
3
4
5
6
7
def hammingWeight(n: int) -> int:
    n = format(n, "032b")
    count = 0
    for c in n:
        if c == "1":
            count += 1
    return count

然后有一个位运算的解法，很trick，如果我自己想我肯定想不出来，代码如下：

1
2
3
4
5
6
def hammingWeight(n: int) -> int:
    count = 0
    while n != 0:
        n = n & (n - 1)
        count += 1
    return count

位运算的相关介绍在这里：位运算有什么奇技淫巧？ - 力扣（LeetCode）的回答。

也就是说，有一个方法，可以把最右边的 1 置为 0，举个具体的例子：

比如十进制的 10，二进制形式是 1010，然后我们只需要把它和 9 进行按位与操作，也就是 10 & 9 = (1010) & (1001) = 1000，也就是把 1010 最右边的 1 置为 0。

规律就是对于任意一个数 n，然后 n & (n-1) 的结果就是把 n 的最右边的 1 置为 0 。

也比较好理解，当我们对一个数减 1 的话，比如原来的数是 …1010000，然后减一就会向前借位，直到遇到最右边的第一个 1，变成 …1001111，然后我们把它和原数按位与，就会把从原数最右边 1 开始的位置全部置零了 …10000000。

有了这个技巧，我们只需要把原数依次将最右边的 1 置为 0，直到原数变成 0，记录总共操作了几次即可。

除了以上方法之外好像还有一种比特位的方法，朋友给我说了解法但是不好放在这里，只能等我看明白之后尝试重写再放出了。

另：这道题同时也是CSAPP的一道lab题。