题目来源：AcWing 801. 二进制中1的个数
一、题目描述
给定一个长度为 n n n 的数列，请你求出数列中每个数的二进制表示中 1 1 1 的个数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，表示整个数列。
输出格式
共一行，包含 n 个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中 1 的个数。
数据范围
1
≤
n
≤
100000
,
1≤n≤100000,
1≤n≤100000,
0
≤
数
列
中
元
素
的
值
≤
1
0
9
0≤数列中元素的值≤10^9
0≤数列中元素的值≤109
输入样例：
5
1 2 3 4 5
输出样例：
1 1 2 1 2
二、算法思想
题型1：求数
x
x
x 的二进制表示中第
k
k
k 位是
0
0
0 还是
1
1
1（最右侧是第0位）？
（1）先把第
k
k
k 位移到最后一位，使用
x
>
>
k
x>>k
x>>k 。
（2）看最后一位是
0
0
0 还是
1
1
1 ，即
x
x
x &
1
1
1 。
因此，将 (1) (2) 两步合并，可以得到
x
>
>
k
&
1
x>>k\&1
x>>k&1 。
查看某个数的二进制表示：
for (int i = 5; i >= 0; i--) printf("%d", x >> i & 1);
题型2：返回
x
x
x 的二进制表示中，最后一位1，即100…00，记为
l
o
w
b
i
t
(
x
)
lowbit(x)
lowbit(x)：
例如：
l
o
w
b
i
t
(
(
1010
)
B
)
lowbit((1010)_B)
lowbit((1010)B)=
(
10
)
B
(10)_B
(10)B，
l
o
w
b
i
t
(
(
101000
)
B
)
lowbit((101000)_B)
lowbit((101000)B)=
(
1000
)
B
(1000)_B
(1000)B
直接记结论：
l
o
w
b
i
t
(
x
)
=
x
&
(
∼
x
+
1
)
=
x
&
−
x
lowbit(x) = x\&(\sim x+1) = x\&-x
lowbit(x)=x&(∼x+1)=x&−x
证明如下图：
l
o
w
b
i
t
(
x
)
lowbit(x)
lowbit(x) 最基本的作用：求数
x
x
x 二进制表示中，数字
1
1
1 的个数。只要每次让
x
−
=
l
o
w
b
i
t
(
x
)
x -= lowbit(x)
x−=lowbit(x) 直到
x
=
0
x=0
x=0为止。
三、代码
#include <iostream>
using namespace std;
int lowbit(int x) { return x & -x; }
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int x, cnt = 0;
scanf("%d", &x);
while (x)
{
x -= lowbit(x); // 每次减去x最后一位1
cnt++;
}
printf("%d ", cnt);
}
return 0;
}