位运算

获取二进制的个位

基本思想

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 代码示例（输出每位【10进制转二进制】）
#include <iostream>

using namespace std;

int main()
{
	int n = 10; // 1010
	
	for (int k = 3; k >= 0; k--) printf("%d",n >> k & 1);

	system("pause");
	return 0;
}

low bit操作

作用

lowbit(x)返回x的最后一位1 x = 1010 , lowbit(x) = 10 x = 10100000000 , lowbit(x) = 100000000

实现

lowbit的实现

应用

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100000, 0≤数列中元素的值≤10e9

输入样例：

1
2

5
1 2 3 4 5

输出样例：

1

1 1 2 1 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>

using namespace std;

int lowbit(int x)
{
	return x & -x;
}

int main()
{
	int n;
	cin >> n;
	while(n --)
	{
		int x;
		cin >> x;

		int res = 0;
		while(x) x -= lowbit(x), res++;

		cout << res << ' ';
	}
	system("pause");
	return 0;
}