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

太过爱你忘了你带给我的痛 2022-12-13 01:19 455阅读 0赞

## 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 = 1
     *  x & ~x = 0
 *  判断是否是 2 的幂次方：n & (n - 1) == 0

文末，再放一个[**参考链接**][Link 1]…

[Link 1]: https://blog.whezh.com/bit-hacks/