按位与
定义
两个运算对象，相同为$0$，不同为$1$。
示例
十进制的
$0, 1, 2, 3, 4, 5, 6, 7, 8$
对应的二进制为
$0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000$
判断十进制数中每一个二进制位是否是$1$。
$1$分别左移$i=0,1,2,3$位，然后与要判断的二进制数进行按位与，如果不是$0$，则说明第$i$位为$1$。
应用
- 判断一个数是不是$2$的幂，再进一步就是统计一个数二进制位为$1$的个数。
$2$的幂有一个特征，就是只有一个二进制是$1$，其余的所有位都是$0$。
而$2$的幂减去$1$会得到所有的二进制位都是$1$，他们按位与，得到所有的二进制位是$0$，即$(2$ ^ $n)$&$(2$ ^ $n-1) = 0$，实际上，这个公式会消去二进制位最右边的一个$1$。 - 按位与实现掩码运算。
按位异或
定义
两个运算对象，相同为$0$，不同为$1$。
规则
只要谨记这两条规则就好。
- 任意两个相等的数亦或都为$0$。
- $0$与任何数亦或都等于那个数。
- 两个有符号数异或，如果符号相同，结果大于$0$，否则小于$0$。
交换律
$a$^$b$ = $b$^$a$
结合律
$a$ ^ $b$ ^ $c$ = $a$ ^ ($b$ ^ $c$)
示例
$12 ^{} 7 = 11$
$12 = 1100$
$7 = 0111$
按位异或得到
$1011 = 11$
$1$ ^ $2$ ^ $3$ ^ $4$ ^ $1$ ^ $2$ ^ $3$ ^ $4$ ^ $5$ = $1$ ^ $1$ ^ $2$ ^ $2$ ^ $3$ ^ $3$ ^ $4$ ^ $4$ ^ $5$
分别对每一位异或，对于每一位来说，其实他们都是没有顺序的，只需要统计每一位有多少个$0$和$1$即可了，重复偶数次的值都相互抵消了，剩下的就是没有抵消的那些。
移位
左移位
$1 \ll 2 $
相当于
$0001 \ll 2 = 0100 = 4$
右移位
$8 \gg 2$
相当于
$1000 \gg 2 = 0010 = 2$
移位和与
移位和与结合起来判断某一位二进制位是否是$1$。
示例
判断$13$从右数的的第$3$个二进制位是否为$1$。
1 | if(13 >> 1 & 1) |