acwing算法基础之基础算法--位运算算法

1 知识点

（一）
n的二进制表示中第k位是0还是1，注意k从0开始编号。

1. 先把第k位移动到最后一位，即n >> k
2. 看个位是几，即x & 1

综合上述，即n >> k & 1。

（二）
lowbit(x)操作，返回x的最后一位1是多少。比如$x=(101000{)}_2，则lowbit(x)=(1000{)}_2$。
公式为lowbit(x) = x & -x。
解释如下。-x在C++中的二进制的表示为取反加1，即~x+1。
应用：求数x的二进制表示中1的个数。

//输入x
//返回res，表示x的二进制表示中1的个数
int lowbit(int x) {
	return x & -x;
}
int res = 0;
while (x) {
	x -= lowbit(x);
	res += 1;
}
1
2
3
4
5
6
7
8
9
10

（三）
C++中的原码，反码（原码取反），补码（原码取反加1）。
C++中的负数用补码来表示。

（四）
通过x & 1来判断x的奇偶性，如果返回1表示它是奇数，如果返回0表示它是偶数。

(x & 1) == 0 //偶数
(x & 1) == 1 //奇数
1
2

（五）
整数a和整数b，求a/b的上取整。

//一般做法
int res = a / b;
if (a % b != 0) res += 1;

//优雅做法
int res = (a + b - 1) / b;
1
2
3
4
5
6

2 模板

//求x的二进制表示中第k位是多少，注意k从0开始编号
x >> k & 1
1
2

//求x的二进制表示中有多少个1
int lowbit(int x) {//x的二进制表示中最低位的1是多少
	return x & -x;
}
int res = 0;
while (x) {
	x -= lowbit(x);
	res += 1;
}
//res就是最终的答案
1
2
3
4
5
6
7
8
9
10