leetcode with python:191. Number of 1 Bits

题目:

Write a function that takes an unsigned integer and returns the number of '1' bits it has

给定32位的unsigned integer,回传它里头有几个1

我一开始想法很单纯,用190.的方式
一个一个位数看是不是1,然后放计数器(反正也才32位XD)

class Solution:    def hammingWeight(self, n: int) -> int:        ans=0        for i in range(32):            if n&1:                ans=ans+1            n=n>>1        return ans

最后执行时间32ms(faster than 91.95%)

后来我又想,既然只是单纯的计数,为何不用count呢(逐渐被讨论区感染

class Solution:    def hammingWeight(self, n: int) -> int:        return bin(n).count("1")

先将其变为二进位字串,算里面的"1"就好
最后执行时间31ms(faster than 93.84%)

不过在我写完逛讨论区的时候,看到一个十分巧妙的解法
这边分享一下,比敝人上面两个没营养的解法好多了

class Solution:    def hammingWeight(self, n: int) -> int:        ans=0        while n:            n=n&(n-1)            ans=ans+1        return ans

到n变为0为止,不断和n-1做&运算,看总共执行了几次
以1100为例,-1就是1011,两者行&运算会变成1000
可以看到最尾端的1就这么轻鬆被消掉了
只要知道消了几次1,就知道该unsigned integer有几个1了
最后执行时间31ms(faster than 93.84%)

那我们下题见