对以下位操作的解释

1
2
state >> i & 1
(1 << i) | state

在代码中，state >> i 和 1 << i 是位操作符的使用，主要用于检查和设置状态变量 state 中的特定二进制位。让我们详细解释这两个表达式的作用。

1. 1 << i

  • 左移操作 (<<): 将数字 1 左移 i 位。
  • 具体作用: 这个操作会生成一个只有第 i 位为 1 的二进制数，其余位为 0。
  • 示例:
    • 1 << 0 结果是 0001 (十进制 1)
    • 1 << 1 结果是 0010 (十进制 2)
    • 1 << 2 结果是 0100 (十进制 4)
    • 1 << 3 结果是 1000 (十进制 8)

2. state >> i

  • 右移操作 (>>): 将数字 state 右移 i 位。
  • 具体作用: 这个操作会将 state 的二进制表示向右移动 i 位，右边补零。
  • 示例:
    • 假设 state = 13 (二进制 1101)
      • 13 >> 0 结果是 1101 (十进制 13)
      • 13 >> 1 结果是 0110 (十进制 6)
      • 13 >> 2 结果是 0011 (十进制 3)
      • 13 >> 3 结果是 0001 (十进制 1)

在代码中的应用

检查第 i+1 个数字是否已被使用

1
if ((state >> i & 1) == 0)

步骤

  1. state >> i: 将 state 右移 i 位，使得我们要检查的第 i+1 个数字的位置变为最低有效位（LSB）。
  2. & 1: 与 1 进行按位与操作，只保留最低有效位的结果。
  3. 如果结果为 0，说明第 i+1 个数字未被使用；如果结果为 1，说明已使用。
  • 示例:
    • 假设 state = 5 (二进制 0101)，我们要检查第 2 个数字（对应 i=1）是否被使用：
      • 5 >> 1 结果是 0010
      • 0010 & 1 结果是 0，说明第 2 个数字未被使用。
    • 假设 state = 5 (二进制 0101)，我们要检查第 1 个数字（对应 i=0）是否被使用：
      • 5 >> 0 结果是 0101
      • 0101 & 1 结果是 1，说明第 1 个数字已被使用。

设置第 i+1 个数字为已使用

1
(1 << i) | state

步骤

  1. 1 << i: 生成一个只有第 i+1 个位置为 1 的二进制数。
  2. | state: 与 state 进行按位或操作，将第 i+1 个位置置为 1，表示该数字已被使用。
  • 示例:
    • 假设 state = 5 (二进制 0101)，我们要将第 2 个数字（对应 i=1）标记为已使用：
      • 1 << 1 结果是 0010
      • 0010 | 0101 结果是 0111 (十进制 7)

总结

  • 1 << i: 生成一个只有第 i+1 位为 1 的二进制数。
  • state >> i & 1: 检查 state 中第 i+1 位是否为 1，即检查第 i+1 个数字是否已被使用。
  • (1 << i) | state: 将 state 中第 i+1 位设置为 1，表示第 i+1 个数字已被使用。

通过这些位操作，我们可以高效地管理和跟踪哪些数字已经被使用过，从而生成所有可能的排列。

原示例

求整数 1~n 所有的排列方式，递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;

public class Main {
    static int n;           // 输入的整数 n
    static int[] path;      // 存储当前排列的数组

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();       // 读取输入的整数 n
        path = new int[n];      // 初始化路径数组

        dfs(0, 0);              // 调用递归函数开始搜索
    }

    static void dfs(int u, int state) {
        if (u == n) {           // 如果当前层数等于 n，说明找到了一个完整的排列
            for (int num : path) {
                System.out.print(num + " ");  // 打印当前排列
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if ((state >> i & 1) == 0) {      // 检查第 i+1 个数字是否已被使用
                path[u] = i + 1;              // 将第 i+1 个数字加入当前排列
                dfs(u + 1, (1 << i) | state); // 继续递归处理下一层
            }
        }
    }
}