今天看到状压dp又忘记了位运算，记录一下笔记

位运算（i>>j&1)是什么意思？

注意二进制下标从右往左从第0位开始递增，
15—> 1 1 1 1
位数 3 2 1 0
i的二进制中，从右往左数，取第j位上的值,判断是1还是0
等价于：
i除以2的j次方，然后与1做与运算，也就是如果i/(2^j)得到的数装换为2进制后，如果最后一位为1，就输出1，最后一位为0就输出0。

int a = i;
a = a / (int)pow(2, j);
if (a % 2 == 0)return 0;
else return 1;

&运算通常用于二进制取位操作，例如一个数 & 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数。

还有左移运算n&(1<<i)

1<<i 是将1左移i位，即从右往左第i位为1，其余位为0；

例如1<<2 则0001->0100
1<<5 000001-> 100000

n&(1<<i)是将左移i位的1与n进行按位与，即为保留n的第i位，其余位置零

如果n第i位为0，则n&(1<<i)的值为0

否则不为0

常用if(n&(1<<i)==0)用于判断n的第i位是否为0

state |(1<<u) 和 ans |=(1<<i),ans +=(1<<i)

在状压dp用state记录状态 有个state|(1<<u),把state的第u位记作1,表示u(从0开始)这个状态被选中
在 AcWing 998. 起床困难综合症 表示可以选择的二进制数为多少并存入答案里，ans|=1<<i / ans+=1<<i;
注：+=与|=并不是完全等价的，即当ans某一位二进制为1
题外话：此题与最大异或对那道题有点类似，那道题是给定n个数，我们以二进制由高到低存进Trie里面,此题给定的一个范围0~m,我们可以和最大异或对一样由高到低确定每一位二进制数，判断每一位填1还是0

~运算符笔记

可以简便记住 ~a=-(a+1);

原码即数绝对值的二进制，最高位设置为符号位，1为负，0为正
正数原码=反码=补码
负数反码=原码除符号位取反，补码=反码+1;
注意取反运算符会将符号位一同取反，而反码，补码运算时是保留了符号位
而且，取反过后的数还是某一个值的补码！！我们要转换为原码输出！！

举例
~5 
5的原码,反码,补码 = 0101
~5 得到某一值的补码 = 1010
最高位为1的符号位，即为负数
负数补码转为原码，来个逆运算，补码-1先转为反码 1001 ，再除符号位取反 1110 = -6
所以~5 的值为 -6
~(-9)
-9的原码 = 11001 反码 = 10110 补码 = 10111
~(-9) 得到 某一值的补码 = 01000
最高位为0的符号位，即为正数
正数原码,反码,补码相同 即为 8
所以~(-9) 的值为 8

lowbit函数求一个数二进制位中1的个数，也可以用来表示多少状态被选中

int lowbit(int x){
    return (x&-x);
}
int nums(int x){
    int res=0;
    while(x){
        x-=lowbit(x),res++;
    }
    return res;
}