acwing算法基础之基础算法--位运算算法
1 知识点
（一）
n的二进制表示中第k位是0还是1，注意k从0开始编号。
- 先把第k位移动到最后一位，即
n >> k - 看个位是几，即
x & 1
综合上述，即n >> k & 1。
（二）
lowbit(x)操作，返回x的最后一位1是多少。比如
x
=
(
101000
)
2
，则
l
o
w
b
i
t
(
x
)
=
(
1000
)
2
x=(101000)_2，则lowbit(x)=(1000)_2
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;
}
（三）
C++中的原码，反码（原码取反），补码（原码取反加1）。
C++中的负数用补码来表示。
2 模板
//求x的二进制表示中第k位是多少，注意k从0开始编号
x >> k & 1
//求x的二进制表示中有多少个1
int lowbit(int x) {//x的二进制表示中最低位的1是多少
return x & -x;
}
int res = 0;
while (x) {
x -= lowbit(x);
res += 1;
}
//res就是最终的答案