【必备算法】位运算：常见位运算符及规律

1.位运算符

左移(<<)：0011 << 1 = 0100，表现在十进制相当于乘2

右移(>>)：0110 >> 1 = 0011，表现在十进制相当于除2

按位与(&)：0011 & 1011 = 0011

按位或(|)：0011 | 1011 = 1011

按位取反(~)：~0011 = 1100

按位异或(^)：0011 ^ 1011 = 1000

相同为0，不同为1；因此异或可用不进位加法来记忆

几个特性：

x ^ 0 = x // 任何数异或0等于自身 x ^ (~x) = 1 // 任何数异或它的非等于1 x ^ x = 0 // 任何数自己异或自己等于0 c = a ^ b =>a ^ c = b, b ^ c = a // 交换两个数 a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c // associative

2.指定位置(n)的位运算

对指定的二进制位进行操作，一般都要配合移位操作（与 n 产生关系，n说的是从最右边（最低位）数起）

将 x 的最右边 n 位清零：x & (~0 << n)

获取 x 第 n 位的值（0或1）：(x >> n) & 1；

原理：1 & 其他值 = 其他值

获取 x 第 n 位的幂值：x & (1 << (n - 1))

仅将第 n 位置为1：x | (1 << n)

仅将第 n 位置为0：x & (~ (1 << n))

将 x 最高位至第 n 位（含）清零：x & ((1 << n) - 1)

注：最左边的二进制位为最高位，最右边的一位为最低位

将第 n 位至第 0 位（含）清零：x & (~((1 << (n + 1)) - 1))

3.位运算实战要点

首先要明确一点，这里使用位运算符的可以直接是二进制形式，也可以是十进制形式；因为位运算符也是会在十进制转为二进制后运算

判断奇偶 x % 2 == 1 -----> (x & 1) == 1；如果最后二进制位=1则是奇数x %2 == 0 ------> (x & 1) == 0 乘 / 除2 x /= 2 -----> x >>= 1；实际上编译器底层也会优化成位运算mid = (left + right) / 2 ------> mid = (left + right) >> 1 x 与 x x & -x = 1x & ~x = 0 判断是否是 2 的幂次方：n & (n - 1) == 0

文末，再放一个参考链接…