题目分析

1. 题目给出一组数字
2. 题目要求我们输出数字二进制的1的个数

方法一：位运算

• 实现思路

  • 我们对数字进行与运算操作，将数字和1取与运算，可以得到其末位是否为1

  • 将目标数字不断右移并迭代，最终计数统计1的个数

while True:
    try:
        n = int(input())
        count = 0
        while n:
            count += n&1        # 位运算统计末位是否为1
            n >>= 1             # 迭代n的值
        print(count)
    except:
        break

复杂度分析

• 时间复杂度：$O(logn)O(logn)$，将数字n转换成二进制后，逐位移动的次数代价是对数级别的
• 空间复杂度：$O(1)O(1)$，未引入额外的空间开销

方法二：字符串

• 实现思路
  • 我们将数字转化为二进制字符串后处理
  • 只要统计出其中1字符的数量即可

while True:
    try:
        n = int(input())        
        print(bin(n).count('1'))        # 转换成二进制，统计二进制中所有1的个数
    except:
        break

复杂度分析

• 时间复杂度：$O(logn)O(logn)$，转换成字符串后需要遍历寻找1的个数，由整数变到二进制的新的长度关系是对数级别的
• 空间复杂度：$O(logn)O(logn)$，转换成字符串后的字符串空间开销