位运算及其技巧
1.补码：
原码为二进制数前带一个符号位
负数为1
正数为0
如110
-2
010 -- > 2
正数的反码与原码相同
负数的反码是除符号位外原码的每一位都取反（1变0 0变1）
正数的补码与原码相同
负数的补码是反码+1
符号位也随之变化
当超过其最大位数时左边多余的位数舍去
如
010 --->反码 补码 010
110-->反码101 --->补码110
关于正0与负0
原码上有两个0，反码上也有，当补码上只有一个0
100 （-0） 000（+0）
反码111 (-0) 000(+0)
补码 1000舍去最左边一位 000 000
所以如果一个数不是0，
若这个数是正数，则它的补码（等于原码）的符号位是0
如果这个数是负数
那么这个数的原码的符号位为1 并且除了符号位至少有一位为1
它的反码的符号位为1 并且除了符号位外的1变成了0，即至少在符号位右边有一个0
这样的话 反码+1 即使有进位，也最终在符号位右边的0上停止进位，这样符号位仍为1
所以如果一个补码全是0，那么就是0
否则：
如果最左边一位是0，则是正数
如果最左边一位是1，则是负数
lowbit(x)= x & (-x)
作用是求\(2^k\)
\(k\)是\(x\)在二进制下最右边开始向左连续\(0\)的个数
0x55555555与0xaaaaaaaa
0x55555555:…10101 31位 奇数位为1 偶数位为0
0xaaaaaaaa:…01010 32位 奇数位为0，偶数位为1，位从1开始
针对int
long long：0x5555555555555555 63位
0xaaaaaaaaaaaaaaaa 64位
交换奇偶位：
如1010-->
0101
只需要取出所有奇数位和所有偶数位
然后奇数位<<1
偶数位>>1
最后合并结果
取出所有奇数位就可以&0x55555555
此时偶数位为0
取出所有偶数位就可以&0xaaaaaaaa
此时奇数位为0
奇数位<<1
偶数位>>1
然后两个相|
为什么相|
因为调整后两个是插空的，空是0
0|0=0
0|1=1
这样就把答案合并了
x&1判断奇数偶数：奇数为1，偶数为0
x&(x-1)判断是不是2的非负整数次幂
0代表是，其余代表不是
注意如果x=0,会误认为 是2的正整数次幂
x&=(x-1)
能够把从右往左最右边的1变成0
可以用来统计x中二进制下1的个数
即ans=0;
while(x)x&=(x-1),++ans;
异或三变量交换：
a=b=a^=b
a=a^b
b=b^a
a=a^b
i+(~i)=-1（十进制-1）
n>>31取得n的正负号，0为正或0
-1为负
((n>>31)^n)-(n>>31)
int来说：
31
longlong：
63
short：
15
判断是否能被2^x整除
a&((1<<x)-1)
为0则能
否则不能
判断某一位是否为1
若从右往左，从0开始
第k位是否为1
就是a&(1<<k)
取<=数a的最大的2的非负整数次幂：
a=a|(a>>1);
a=a|(a>>2);
a=a|(a>>4)
a=a|(a>>8)
a=a|(a>>16)
return (a+1)>>1
这是int型的
longlong的要再加一行
a=a|(a>>32)
总之和要等于数据类型所能表示的最大的数的2的次幂的指数
前提是整数
如int 31
long long 63
short 15
unsigned的与signed的最大大小相同
即超过signed的数据类型的最大值就会溢出，即使使用unsigned
另外更换数据类型时参数返回值，main中定义，以及>>1 ---> >>1ll或>>1ull都要修改
判断x y符号是否相同
x^y>=0则相同
否则则不同
0除外
-x=~x+1
0也使用
得到一个二进制数从右往左的第一个1及其左边的数
x&(-x)
用&和^完成加法：
^是不进位加法
&是取进位，但是进位是要加在这一位左边
所以要<<1
然后再用此法把这2个数加起来，直到一个数为0为止，返回另一个数，但是比一般加法慢很多
区间&
：
[l,r]的连续区间的与运算结果（注意不是给定数组a[l]~a[r]的与，而是数l到数r的与，l r可以很大，直接用st表会mle+tle）
我们可以O(logn)求解
可以先求出l r二进制下左边相同的最大长度的一段，然后这段相与=原段，故这段保留
然后右边从左开始第一位肯定不同（相同就算进左边了）
而要想让这一位不同，则这一位右边的数肯定要加过来，所以右边每一位0和1都取到
所以右边答案为0
所以程序如下：
a=0
while(m!=n){
m>>=1
n>>=1
++a
}
return m<<a
区间|
那么左边|后等于原段
右边因为每一位有过1
所以右边答案答案为1
所以：
a=0
while(m!=n){m>>=1;
n>>=1;
++a;
}
return (m<<a)+((1<<a）-1）
