位运算

n的二进制表示中第k位是几

  1. 先把第k位移到最后一位 n >> k
    n >> k的操作不会改变n本身的值
  2. 看个位是几 x & 1

两个步骤加起来就是n >> k & 1

输出10的二进制数代码示例

1
2
LL n = 10;
for (LL k = 3; k >= 0; k--) cout << (n >> k & 1);

lowbit(x)：返回x的最后一位1

原理和实现

lowbit(x)操作相当于x & -x=x & (~x + 1)

自己拿一个数模拟一下就知道了为什么了

代码实现（stl没有）:

1
2
3
LL lowbit(LL x) {
	return x & -x;
}

应用

计算二进制中1的个数，代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

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

int main() {
	LL n;
	cin >> n;
	while (n--) {
		LL x, res = 0;
		cin >> x;
		while (x) x -= lowbit(x), res++;
		cout << res << " ";
	}
	
	return 0;
}