深入浅出位运算
我们都知道，计算机底层系统是根据二进制逻辑思想构造的，所以我们现在讲的位运算将会是针对二进制为底数的按位运算
如果不懂进制的话，建议先看: 进制原理
位运算除了可以实现：优化计算，状态压缩，倍增和树状数组等重要算法和数据结构以外，还有许多灵活的奇淫用法，所以觉得相当有必要复习！
基础运算
使用位运算可以让程序运行效率大大提高
C语言 | Pascal语言
——- + ————-
与 a & b | a and b
或 a | b | a or b
异或 a ^ b | a xor b
取反 ~a | not a
左移 a << b | a shl b
右移 a >> b | a shr b
&和&&不同，|和||也不同！
对于上面的基础知识，大家可以自查手册
位运算应用：
1，判断奇偶性：
if（a&1==1）{奇数；}
1的二进制为0000000……01，所以，a&1的其他位数全部舍去，最后一位为1则为1，为0则为0；
2，求得与之最接近的奇数（偶数）
a=a|1;必把最后一位改为1，其他位保持不变，则得到大于等于a的最近的奇数（如果a本身就是奇数也可以保持）
a=a|1-1；得到小于等于a的最近的偶数
当然也可以(a>>1)<<1;也就是把二进制最后一位舍去，效果同上
如果只是想改变其奇偶性，就a^=1;,也就是其他位保持不变末尾0^1=1,1^1=0，奇偶转化
也可以把特定一位(或者末尾k位)变成1（或者取反？）
a|=(1<<k);
a|=(（1<<(k+1)）-1)
3，不用临时变量进行交换
思路：^的逆运算是^,所以a^b^b=a；
a^=b;此时a=a^b
b^=a;此时b=(a^b)^b=a
a^=b;此时a=a^(a^b)=b
类似思路甚至可以想到(减是加的逆运算)：
a+=b; a=a+b
b=a-b; b=a+b-b=a;
a-=b; a=a+b-a=b
4，乘（或除以并取整）2或2的次方
a<<1; a的二进制位向左移动一位，相当于乘以2
a<<2; 相当于乘以两次2，也就是*(2^2);
a<<4;乘以2的4次方
a>>1；除以2，向下取整；经常用于二分，速度增加很多
由此得到舍去后n位：(a>>n)<<n;也就是把后n位二进制变为0
5，取二进制末尾几位：
a&((1<<(k+1))-1）
k是位数，1左移k位后位0000……0010000<-k个0->00;
减去1之后为000……0001111……111（k个1）
则k位之前全舍去，k位之后全保留
由此可以按照(1<<k)-1构造这样的数列
也可以单独取出k位上的数：
a>>(k-1)&1
甚至可以把从最右开始几位连续的1变成0：a&（a+1）//a+1即为转化后几位1为0，只是多了一个新的1，
类似的，可以直接去掉从最右开始的第一个1：a&（a-1）
取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1
lowbit！！！
去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1))
计算机储存负数的本质：2进制中，最高位为0是正，为1是负数，所以最大的正数加一后变为最小的负数，二进制最大的数（11……）反而是-1
所以，~a=-a-1，如1 00001 ~1 11110（-2）
11110 11111 00000 00001
-2 -1 0 1
在此情况下，一个数加上它的相反数，得到2的位数次方（刚好溢出，剩余部分为0），这种储存方法为补码，一个数的补码是这个数取反加一（也就是负数）
是不是有些看不懂？没关系因为我还没讲
主要讲一下上面标记了lowbit的那个计算方法
也就是：只保留最低的二进制位
就比如 ： 11001101000 保留之后就是： 00000001000
为什么讲一下这个呢？因为这是许多数据结构的重点，比如树状数组
首先，回忆一下我们是怎么操作的:
x and (x xor (x - 1))
先模拟一下看结果：
x 11001101000
x-1 11001100111
x xor (x - 1) 00000011111
x and (x xor (x - 1)) 0000001000
非常完美，但是为什么呢？
首先，x-1，最低位的1变成0，更低位的0变成1
再与原数xor（xor有一个定则：两数相同就变0，两数不同就变1）
所以就得到 原最低位的1变回1 和 原更低位的0变为1
而其他位都为0 所以，和原数一and
更高位为0，更低位（原来是0）为0 ，原来为1的最低位的位还是1
这就是lowbit的位运算求法，不需要按位枚举！
当然了，其实还有另一种lowbit求法，更好理解：
x and -x
是不是很简短，按照上面的原理，原本意思应该是：
x and (~(x-1))
这个嘛，就交给大家思考了！
Over~
