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 ,则 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就是最终的答案