题目描述

给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。

输入格式
第一行包含整数n。

第二行包含n个整数，表示整个数列。

输出格式
共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。

数据范围
1≤n≤100000,
0≤数列中元素的值≤10^9

样例

输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2

算法1

位运算

n的第k位：n>>k&1
lowbit(x),返回x的最后一位1
x&(-x) = x&(~x+1)
题目解法：每一次把最后一位1去掉，看一共去掉多少次

python 代码

def lowbit(x):
    return x&-x
if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        res=0
        while a[i]:
            a[i]-=lowbit(a[i])
            res+=1
        print(res,end=" ")