【题目描述】
给定一个长度为 n n n的数列,请你求出数列中每个数的二进制表示中 1 1 1的个数。
【输入格式】
第一行包含整数 n n n。
第二行包含 n n n个整数,表示整个数列。
【输出格式】
共一行,包含 n n n个整数,其中的第 i i i个数表示数列中的第 i i i个数的二进制表示中 1 1 1的个数。
【数据范围】
1 ≤ n ≤ 100000 1≤n≤100000 1≤n≤100000
0 ≤ 数 列 中 元 素 的 值 ≤ 1 0 9 0≤数列中元素的值≤10^9 0≤数列中元素的值≤109
【输入样例】
51 2 3 4 5
【输出样例】
1 1 2 1 2
【分析】
我们可以写一个 l o w b i t ( x ) lowbit(x) lowbit(x)函数返回 x x x的二进制中最低位的 1 1 1所表示的数,那么怎么实现这个功能呢?假设 x = ( 1100100 ) B x=(1100100)_B x=(1100100)B,那么 − x = ( 0011011 ) B + 1 = ( 0011100 ) B -x=(0011011)_B+1=(0011100)_B −x=(0011011)B+1=(0011100)B,则 x & − x = ( 0000100 ) B x&-x=(0000100)_B x&−x=(0000100)B,也就是 x x x的最低位 1 1 1所表示的数。然后回到本题,我们需要快速计算出某个数的二进制表示中有几个 1 1 1,那我们就可以循环每次将这个数 x x x减去 l o w b i t ( x ) lowbit(x) lowbit(x),也就是每次循环都把 x x x的最低位 1 1 1减去,每减一次答案加一,等这个数减为 0 0 0时答案就是这个数中 1 1 1的个数。
【代码】
#include