【算法技巧】位运算

短命女 2024-02-17 09:45 42阅读 0赞

#### 目录 ####

*  1.概述
 *  2.位运算技巧
 *   *  2.1.与运算 (&)
     *   *  2.1.1.判断奇偶性
         *  2.1.2.判断一个数是否是 2 的幂
         *  2.1.3.将英文字母转换为大写
         *  2.1.4.代替取模运算
     *  2.2.或运算 (|)
     *   *  2.2.1.将英文字母转换为小写
     *  2.3.异或运算 (^)
     *   *  2.3.1.消除成对相同的数
         *  2.3.2.不使用临时变量来交换两个数
         *  2.3.3.进行英文字母大小写互换
         *  2.3.4.判断两个数是否异号
     *  2.4.取反运算 (~)
     *   *  2.4.1.自增
         *  2.4.2.自减
     *  2.5.移位运算 (<<、>>、>>>)
     *   *  2.5.1.乘以 2
         *  2.5.2.除以 2
 *  3.应用

## 1.概述 ##

（1）位运算是一种直接对二进制位进行操作的运算方式。它们是在计算机中对数据的底层操作，通常在位级别上进行，不考虑数据的整体值。在 Java 中，位运算符有以下几种：

*  **与运算 (&)**：对两个操作数的每一位进行与操作，只有当对应的位都为 1 时，结果为 1，否则为 0。
 *  **或运算 (|)**：对两个操作数的每一位进行或操作，只要对应的位至少有一个为 1，结果为 1，否则为 0。
 *  **异或运算 (^)**：对两个操作数的每一位进行异或操作，只有当对应的位不同时，结果为 1，否则为 0。
 *  **取反运算 (~)**：对一个操作数的每一位进行取反操作，将 0 变为 1，将 1 变为 0。
 *  **左移运算 (<<)**：将一个操作数的所有位向左移动指定的位数，低位补 0。
 *  **右移运算 (>>)**：将一个操作数的所有位向右移动指定的位数，高位的处理取决于具体情况。
 *  **无符号右移运算 (>>>)**：将一个操作数的所有位向右移动指定的位数，高位总是补 0。

（2）位运算常用于编程中的一些特定场景，如**位掩码**、**位集合操作**、**优化算法**、**设计**以及**操作硬件**等。它们在处理位级别的数据和优化性能方面非常有用。

> 有关位运算的更多技巧，可以参考 [Bit Twiddling Hacks][]。

## 2.位运算技巧 ##

### 2.1.与运算 (&) ###

#### 2.1.1.判断奇偶性 ####

**判断奇偶性**：位运算中最低位为 1 表示奇数，为 0 表示偶数。

(n & 1) == 1	// n 为奇数
    (n & 1) == 0	// n 为偶数

#### 2.1.2.判断一个数是否是 2 的幂 ####

如果一个数是 2 的幂，那么它的二进制形式中只有最高位为 1，其他位都是 0。

(n & (n - 1)) == 0	// x 是 2 的幂
    (n & (n - 1)) == 1	// x 不是 2 的幂

> n & (n - 1) 的作用是**消除数字 n 的二进制表示中的最后一个 1**。因此，如果 n 是 2 的幂，那么 n 的二进制表示中只有一个 1，所以 n & (n - 1) 的结果必为 0。

#### 2.1.3.将英文字母转换为大写 ####

我们可以通过将小写字母与下划线 ‘\_’ 进行与操作，将其转换为对应的大写字母。

(char) ('n' & '_') = 'N'
    (char) ('N' & '_') = 'N'[添加链接描述](https://xgqngu.blog.csdn.net/article/details/130137431)

*  在位运算中，字符在内存中以数字的形式表示。在大部分字符编码中（如 ASCII 码），**大写字母的编码值比小写字母的编码值要小**；
 *  在 ASCII 编码中，大写字母和小写字母的 ASCII 码值之间的差值为固定的 `32`（或二进制的 `0010 0000`），例如，字母 ‘A’ 的 ASCII 码值为 `65`，而字母 ‘a’ 的 ASCII 码值为 `97`，它们之间的差值就是 32。
 *  而 ‘\_’ 的二进制表示为 `0101 1111`，小写字母 a-z 的 ASCII 值范围为 97-122，即 0110 0001-0011 1101；
 *  那么**小写字母与 ‘\_’ 相与后，相当于其对应 ASCII 值减少了 32，因此也就转换为了对应的大写字母**。

#### 2.1.4.代替取模运算 ####

（1）一般来说，我们要求 h 除以 n 的余数，会通过取模运算 (%)，即 h % n。但当 n 是 2 的幂次方时，我们可以使用位运算来代替取模运算，从而达到提高计算效率的目的，即：

h % n == hash & (n - 1)	// n 是 2 的幂次方

（2）当 n 是 2 的幂次方时，它的二进制表示为 `100…00（n 个 0）`。这意味着 n - 1 的二进制表示为 011…11（n 个 1）。因此，按位与运算 h & (n - 1) 实际上是将 h 的二进制表示的最后 n 位保留，其他位都设为 0，起到了取模的效果。

（3）在这种情况下进行替换有一些具体的应用场景，例如 HashMap 中数组 table 长度被设置为 2 的 n 次方中的一个目的就是上面提到的提高计算效率，具体细节可以参考 [Java 基础——HashMap 底层数据结构与源码分析][Java _HashMap]这篇文章中的 3.1 章节。

### 2.2.或运算 (|) ###

#### 2.2.1.将英文字母转换为小写 ####

我们可以通过将大写字母与空格 ’ ’ 进行或操作，将其转换为对应的小写字母。

(char) ('N' | ' ') = 'n'
    (char) ('n' | ' ') = 'n'

*  其原理与上面的通过与操作将英文字符转换为大写类似，空格字符在 ASCII 编码中的值为 32（十进制），其二进制表示为 `0010 0000`。
 *  而大写字母 A-Z 的 ASCII 值范围为 65-90，即 `0110 0001-0011 1101`；
 *  那么**大写字母与 ’ ’ 相或后，相当于其对应 ASCII 值增加了 32，因此也就转换为了对应的小写字母**。

### 2.3.异或运算 (^) ###

#### 2.3.1.消除成对相同的数 ####

（1）异或运算有两个非常重要的性质：

*  一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。
 *  一个数和它本身做异或运算结果为 0，即 a ^ a = 0；

（2）其中，第二条性质明显有一个重要的用途，即**消除成对相同的数**，如果再结合异或运算的交换律，那么我们可以很迅速地解决 [136.只出现一次的数字][136.]这题，即**给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素**。

class Solution {
        
    	public int singleNumber(int[] nums) {
        
    		int single = 0;
    		/*
    			对于本题，只要把所有数字进行异或，成对的数字就会变成 0，落单的数字和 0 做异或还是它本身，
    			所以最后异或的结果就是只出现⼀次的元素。
    		*/
    		for (int num : nums) {
        
    		   single ^= num;
    		}
    		return single;
    	}
    }

> [268.丢失的数字][268.] 这题也可以通过这个技巧来解决。

#### 2.3.2.不使用临时变量来交换两个数 ####

int a = -1;
    int b = 2;
    a ^= b;
    b ^= a;
    a ^= b;
    System.out.println("a = " + a);     // a = 2
    System.out.println("b = " + b);     // b = -1

其实，上面不使用临时变量来交换两个数是基于 `a ^ a = 0` 这一性质实现的，具体推导过程如下：

a ^= b;		// a1 = a ^ b
    b ^= a;		// b1 = b ^ a1 = b ^ (a ^ b) = a
    a ^= b;		// a2 = a1 ^ b1 = (a ^ b) ^ a = b

#### 2.3.3.进行英文字母大小写互换 ####

(char) ('n' ^ ' ') = 'N'
    (char) ('N' ^ ' ') = 'n'

*  其原理与上面的通过与操作将英文字符转换为大写类似，空格字符在 ASCII 编码中的值为 32（十进制），其二进制表示为 `0010 0000`。
 *  而大写字母 A-Z 的 ASCII 值范围为 65-90，即 `0110 0001-0011 1101`；
 *  而小写字母 a-z 的 ASCII 值范围为 97-122，即 `0110 0001-0011 1101`；
 *  **大小写字母与 ’ ’ 相异后，小写字母对应 ASCII 值减少了 32，大写字母对应 ASCII 值增加了 32，因此也就进行了英文字母大小写互换**。

#### 2.3.4.判断两个数是否异号 ####

计算机底层中整数通常使用**补码**来表示，通过位运算判断两个数是否异号的原理是就是利用了**补码表示中最高位符号位的特性**。默认情况下，整数的最高位为符号位，0 表示正数，1 表示负数。通过位运算判断两个数是否异号的步骤如下：

*  对两个数进行异或运算 (^)。异或运算的结果在二进制表示中，两个数对应位相同则为 0，相异则为 1。
 *  如果结果小于 0，则说明这两个数异号；如果结果大于 0，则说明这两个数同号。

int a = 1;
    int b = 2;
    System.out.println(((a ^ b) < 0));  // false，a 和 b 同号
    
    int c = -1;
    int d = 2;
    System.out.println(((c ^ d) < 0));  // true，a 和 b 异号

### 2.4.取反运算 (~) ###

#### 2.4.1.自增 ####

int n = 2;
    n = -~n;
    System.out.println(n);	// 3

#### 2.4.2.自减 ####

int n = 2;
    n = ~-n;
    System.out.println(n);	// 1

### 2.5.移位运算 (<<、>>、>>>) ###

#### 2.5.1.乘以 2 ####

在二进制表示中，将一个数乘以 2 就等于将它向左移动 1 位，低位补 0。

int n = 3;
    n <<= 1;
    System.out.println(n);		// 6

#### 2.5.2.除以 2 ####

在二进制表示中，将一个数乘以 2 就等于将它向右移动 1 位，高位补符号位。

int n = 4;
    n >>= 1;
    System.out.println(n);		// 2

> 更多有关 Java 中移位运算符的细节可以参考 [Java 基础面试题——运算符][Java]这篇文章。

## 3.应用 ##

大家可以去 LeetCode 上找相关的位运算的题目来练习，或者也可以直接查看 [LeetCode 算法刷题目录 (Java)][LeetCode _ _Java] 这篇文章中的位运算章节。如果大家发现文章中的错误之处，可在评论区中指出。

[Bit Twiddling Hacks]: http://graphics.stanford.edu/~seander/bithacks.html
[Java _HashMap]: https://xgqngu.blog.csdn.net/article/details/130137431
[136.]: https://xgqngu.blog.csdn.net/article/details/120247699
[268.]: https://xgqngu.blog.csdn.net/article/details/124055778
[Java]: https://xgqngu.blog.csdn.net/article/details/129033512
[LeetCode _ _Java]: https://xgqngu.blog.csdn.net/article/details/122477673