leetcode_位运算 191.位1的个数

191. 位1的个数

• 给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中设置位 (set bit，指在某数的二进制表示中值为 1 的二进制位)的个数（也被称为汉明重量）。
  

1. 字符串 + 列表

1. class Solution(object):
2.     def hammingWeight(self, n):
3.         """
4.         :type n: int
5.         :rtype: int
6.         """
7.         a = ""
8.         a = str(bin(n))[2:]
9.         # 将整数转化为二进制字符串
10.         b = [int(char) for char in a]
11.         # 将二进制字符串转换为整数列表
12.         count = 0
13.         for i in range(len(b)):
14.                 # 遍历列表
15.             if b[i] == 1:
16.                 count += 1
18.         return count

复制代码

• 时间复杂度: O(log(n)) ，由于n的二进制表示大约需要 log(n) 位
  
• 空间复杂度: O(log(n))
  

2. 位运算

1. class Solution(object):
2.     def hammingWeight(self, n):
3.         """
4.         :type n: int
5.         :rtype: int
6.         """
7.         count = 0
8.         while n:
9.             count += n & 1  
10.             # 通过与运算判断最低位是否为1
11.             n >>= 1  
12.             # 右移一位，继续检查下一个二进制位
13.         return count

复制代码

• 时间复杂度: O(log(n))
  
• 空间复杂度: O(1)
  

3. 取余和整数除法

1. class Solution(object):
2.     def hammingWeight(self, n):
3.         a = 0
4.         if n == 0:
5.             return 0
6.         while n > 0:
7.             a += n % 2  
8.             # 判断最低位是否为1
9.             n //= 2  
10.             # 将n右移一位
11.         return a

复制代码

• 时间复杂度: O(log(n))
  
• 空间复杂度: O(1)
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。