位运算及其技巧

位元算基本介绍

位运算包括左移、右移、与、或、异或、否。在c/c++种的符号分别是<<、>>、&、|、^、～。

<<(左移)：5101左移一位变成101010,效果是52。a<<b的效果是a\2^b。

>>(右移)：5101右移一位变成210,效果是5/2。a>>b的效果是a/2^b。

&(与)：1和1才是1，其他情况（0和1，1和0，0和0）都是0。

|(或)：0和0才是0，其他情况（0和1，1和0，1和1）都是1。

^(异或)：相同(0和0，1和1)为0，不同（1和0，0和1）为1。也被称为不进位的加法，即半加运算。

~(否)：按位取反，即0变成1，1变成0。

技巧

1. 1 << n,表示2ⁿ
2. n & 1,表示n的最右位数字，所以n >> i & 1表示n的第i位数字，i为从0开始，从右往左数的结果，
3. a^a=0,a^0=a,a^b^c=(a^b)^c=a^(b^c)=a^c^b
4. ｜运算常用来拼接两个数，比如1000和100，拼接结果为1100