一些与位运算有关的操作

位运算基础

基础运算：

a&b//按位与
a|b//按位或
a^b//按位异或
a<<2//按位左移
a>>4//按位右移
~a//按位取反
//特别注意，这些位运算的优先级非常小，甚至比=还小
//所以进行位运算时要注意勤补括号
//经典错误：a==a&1，a&1!=1
//这里因为&的优先级小于==，所以实际上是先进行a==a返回1，再进行1&1返回1
//从而结果本身与a无关

一些性质：

a^a=0//在异或下，一个数为自身的逆元
a^0=a//任何数异或0都是其自身
(a^b)^c=a^(b^c)//异或满足结合律

a|0=a//任何数或0都是其本身
a|a=a
a|(b|c)=(a|b)|c//或满足结合律

a&0=0//任何数与0都是0
a&~a=0
a&a=a
a&(b&c)=(a&b)&c//与满足结合律

a&(b|c)=a&b|a&c
a|(b&c)=a|b&a|c
//可参考集合的交与并运算来记
a^(b|c)=a^b|a^c//与^有关的唯一一个分配率

a+b=a&b+a^b//全加器

//负数右移的时候，最左边补1，但是左移的时候，最右边补0

与位运算有关的构造：

1<<k//此构造经常用于进行二进制数位的单点修改，或者单点查询，比如：
a|(1<<k)//将a的第k+1位置1
a&(1<<k)//查询a的第k+1位是否为1
//(a>>k)&1//也可以这样写
a&1//判断a是否为奇数
a^(1<<k)//将a的第k+1位取反

(1<<k)-1//构造k个连续的1
((1<<a)-1)<<b//构造完a个连续的1后，向左推动b个单位
(((1<<a)-1)<<b)&num//获取num指定二进制位区间的数位
//((1<<a)-1)&(num>>b)//写成这样也行
(((1<<a)-1)<<b)|num//将num指定二进制位区间的数位强制置1
(~(((1<<a)-1)<<b))&num//将num指定二进制位区间的数位强制清零
(((1<<a)-1)<<b)^num//将num指定二进制位区间的数位强制取反
(a&b)==b//查询b的各个为1的数位，a是否也都为1
a>>=1//a除2，常见于快速幂

x&(x-1)//将x最后一个1置0
(x&(x-1)==0)//判断x是不是2的整数次幂
x|(x+1)//将x最后一个0置1
ll lowbit(ll x){return x&-x;}//返回二进制位的最后一个1
int msb(ll x){return x>0?log2l(x)+1:0;}//获取二进制有效位数（记得#include<cmath>）

拆位（数位DP的一种）

通过枚举二进制位数，逐个确定答案的方法。

//例：
ll ans=0;
FOR(k,29,0){//枚举位数。顺序看题目要求
    ans|=(1<<k);//ans的k+1位置1
    //对ans进行各种操作的相关代码，以决定这位该不该置1
    if(xxx&ans!=ans){//如果不满足某条件，撤回操作，这里的条件是，xxx是否在ans为1的数位上为1
        ans^=(1<<k);//撤回置1操作
    }
}