leetcode_位运算191.位1的个数

191. 位1的个数 给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中设置位 (set bit，指在某数的二进制表示中值为 1 的二进制位)的个数（也被称为汉明重量）。 1. 字符串 + 列表 class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ a = "" a = str(bin(n))[2:] # 将整数转化为二进制字符串 b = [int(char) for char in a] # 将二进制字符串转换为整数列表 count = 0 for i in range(len(b)): # 遍历列表 if b[i] == 1: count += 1 return count 时间复杂度: O(log(n)) ，因为n的二进制表示大约需要 log(n) 位空间复杂度: O(log(n)) 2. 位运算 class Solution(object): def hammingWeight(self, n): """ :type n: int :rtype: int """ count = 0 while n: count += n & 1 # 通过与运算判断最低位是否为1 n >>= 1 # 右移一位，继续检查下一个二进制位 return count 时间复杂度: O(log(n))空间复杂度: O(1) 3. 取余和整数除法 class Solution(object): def hammingWeight(self, n): a = 0 if n == 0: return 0 while n > 0: a += n % 2 # 判断最低位是否为1 n //= 2 # 将n右移一位 return a 时间复杂度: O(log(n))空间复杂度: O(1)