0191._number_of_1_bits.md

Navigation

• Navigation
• Links:
• Solution 1 Python API
• Solution 2 十进制转二进制
• Solution 3 位运算
• Solution 4 位操作优化
• 位运算的时间复杂度和空间复杂度

Links:

1. https://leetcode.com/problems/number-of-1-bits/
2. https://leetcode-cn.com/problems/number-of-1-bits/

Solution 1 Python API

class Solution:
    def hammingWeight(self, n):
        return bin(n).count('1')
        

Solution 2 十进制转二进制

其实是Solution 1的自己实现

class Solution:
    def hammingWeight(self, n):
        count = 0

        while n:
            res = n % 2
            if res == 1:
                count += 1
            n //= 2

        return count

Solution 3 位运算

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

---

Go

package main

func hammingWeight(num uint32) int {
	count := 0

	for num != 0 {
		if num & 1 != 0 {
            count++
        }

		num >>= 1
	}

	return count
}

Solution 4 位操作优化

我们不再检查数字的每一个位，而是不断把数字最后一个 11 反转，并把答案加一。 关键是对于任意数字 n ，将 n 和 n - n−1 做与运算，会把最后一个 1 的位变成 0。

class Solution(object):
    def hammingWeight(self, n):
        count = 0

        while n:
            count = count+1
            n = n&(n-1)
            
        return count

---

Go

package main

func hammingWeight(num uint32) int {
	count := 0

	for num != 0 {
		count++
        num = num & (num-1)
	}

	return count
}

位运算的时间复杂度和空间复杂度

int最多32位, 也就是最坏情况下是O(32), 也就是常数时间复杂度, 大O表示法就是写为O(1). 空间复杂度为O(1)，没有用额外的空间。