算法题中常用的位运算

清疚 2024-03-30 10:31 53阅读 0赞

#### 文章目录 ####

*   *  为什么使用位运算？
     *  十进制和二进制之间的转化
     *   *  短除法（十进制转二进制）
         *  幂次和（二进制转十进制）
     *  位运算符
     *   *  异或运算（xor）
         *  指定位置的位运算
         *  位运算实战要点

### 为什么使用位运算？ ###

机器采用二进制对数值进行表示、存储和运算，在程序中恰当的使用二进制，可以提高运行效率。

### 十进制和二进制之间的转化 ###

#### 短除法（十进制转二进制） ####

示例：7的二进制是多少？  
第一步： 7 除以 2 等于 3，余数为 1；  
第二步： 3 除以 2 等于 1，余数为 1；  
第三步： 1 除以 2 等于 0，余数为 1；  
等于0时停止，倒着把余数连起来就是二进制，如上：7的二进制为 111。

#### 幂次和（二进制转十进制） ####

示例：将二进制1101转为十进制是多少？  
2^3 + 2^2 + 2^0 = 8 + 4 + 1 = 13

### 位运算符 ###

![算法题中常用的位运算][18fbd9eff0f24fad80ae2097b3f4fafd.png_pic_center]

> 注：在Java中，>> 为算术右移，移动时最高位补符号位，不一定是0。如果是负数（即最高位符号位为1）。  
> 如果需要右移时最高位补0，忽略符号位，那么应该使用逻辑右移 >>>，多了一个尖括号 。

#### 异或运算（xor） ####

相同为0，不同为1。

**异或运算的特点和应用：**

*  **x ^ 0 = x :** 一个数与0异或，结果还是其自己。
 *  **x ^ x = 0 :** 一个数与自己异或，结果为0。
 *  **结合律：** a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
 *  **成对变换：**(0 ^ 1 = 1, 1 ^ 1 = 0), (2 ^ 1 = 3, 3 ^ 1 = 2), (4 ^ 1 = 5, 5 ^ 1 = 4) … (2n ^ 1 = 2n + 1, (2n + 1) ^ 1 = 2n)
 *  **交换两个数：** 如交换a与b, a = a ^ b; b = a ^ b; a = a ^ b;
    
    1.  a = a ^ b;
    2.  b = a ^ b = a ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a;
    3.  a = a ^ b = a ^ b ^ a = a ^ a ^ b = 0 ^ b = b;

#### 指定位置的位运算 ####

二进制数，从右边数的第 n 位, n 从 0 开始。

*  获取 x 在二进制下的第 n 位：（x >> n）& 1
 *  将 x 在二进制下的第 n 位设置为 1 ：x | (1 << n)
 *  将 x 在二进制下的第 n 位设置为 0 ：x & (~(1 << n))
 *  将 x 在二进制下的第 n 位取反：x ^ (1 << n)
 *  将 x 最右边的 n 位清零：x & (~0 << n)
 *  将 x 的最高位到第 n 位（包含）清零：x & ((1 << n) - 1)

#### 位运算实战要点 ####

**判断奇偶：**

*  偶数：x % 2 == 0 => (x & 1) == 0
 *  奇数：x % 2 == 1 => (x & 1) == 1

**除以2的幂次：**

*  x / 2 = x >> 1
 *  x / 2 ^ n = x >> n: x 除以 2 的 n 次方 等于 x 右移 n 位。
 *  mid = (left + right) / 2 = (left + right) >> 1

**最低位:**

*  得到最低位的1: x & -x 或 x & (~x + 1)
 *  清零最低位的1: x & (x - 1)

[18fbd9eff0f24fad80ae2097b3f4fafd.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/91867e336ee7434e942fc3b50bf21d5b.png