剑指Offer[15]-二进制中1的个数

题目

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

python代码

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        total_n = 0
        if n<0:
            n = -n
        while n!=0:
            total_n += n&1
            n >>= 1
        return total_n

上述解法的思路比较常规,每次取出二进制的最后一位,此时我们需要遍历二进制的每一位。

  • n&1:取出二进制的最后一位,与n%2作用一样。
  • n>>=1:n右移一位,与n//2作用一样。

拓展

总认为会有其它的做法,果然,在leetcode的讨论区发现了一种更巧妙的方法。

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        total_n = 0
        if n<0:
            n = -n
        while n!=0:
            n &= (n-1)
            total_n+=1
        return total_n

和第一种方法不同的是,这里的n&=(n-1)非常巧妙,我们来举例说明:

第一次
n:            1 0 1 0 1
n-1:         1 0 1 0 0
n&(n-1):   1 0 1 0 0

第二次
n:            1 0 1 0 0
n-1:         1 0 0 1 1
n&(n-1):   1 0 0 0 0

第三次
n:            1 0 0 0 0
n-1:         0 1 1 1 1
n&(n-1):   0 0 0 0 0

通过上面的例子可以看到没进行一次n&(n-1),相当于将n的最右侧的一位1置为0,这样我们整个算法计算的次数仅仅是二进制中1的个数,而第一种方法需要遍历二进制的每一位,时间复杂度由O(N)变为O(M)(M<=N,其中N为二进制的位数,M为二进制中1的个数)

发表评论

电子邮件地址不会被公开。