0191._number_of_1_bits.md

191. Number of 1 Bits

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/number-of-1-bits/description/

内容描述

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Example 1:

Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011 
Example 2:

Input: 128
Output: 1
Explanation: Integer 128 has binary representation 00000000000000000000000010000000

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

转成二进制，数1的个数

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count('1')

思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******

有wikipedia的题目 Hamming Weight

用wikipedia的解法：

原理是在于每次使用x & x-1 总会把低位的数字给置0

比如

3 = 011  2 = 010  3 & 2 = 010 cnt = 1
2 = 010  1 = 001  2 & 1 = 000 cnt = 2

比如

9 = 1001  8 = 1000  9&8 = 1000 cnt = 1
8 = 1000  7 = 0111  8&7 = 0000 cnt = 2

减1操作将最右边的符号从0变到1，从1变到0，与操作将会移除最右端的1。如果最初X有N个1，那么经过N次这样的迭代运算，X将减到0。下面的算法就是根据这个原理实现的。

所以关键点是每次都会把最右边的1变成0.

AC代码

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