状态压缩：位运算预备知识与应用

"状态压缩是一种在计算机科学和信息学中常用的技术，特别是在算法设计和数据结构中。状态压缩的主要目的是减少存储和处理大量状态所需的空间。在这个讲稿中，我们将探讨状态压缩的基本概念，以及如何利用位运算进行高效的状态表示。 状态压缩的核心思想是将一组可能的状态编码为一个较小的整数，通常是通过位操作来实现。这种技术常用于解决具有大量离散状态的问题，比如棋盘游戏、图论问题等，通过位运算快速地切换和检查状态。 首先，我们需要了解位运算的基础知识。在C/C++中，位运算有以下几种类型： 1. 按位与（&）：对应位都是1时结果才为1，否则为0。在Pascal中对应的操作符是`and`。 2. 按位或（|）：至少有一个对应位为1时结果为1，否则为0。Pascal中对应的是`or`。 3. 按位取反（~）：将每一位取反，0变为1，1变为0。Pascal中的`not`。 4. 按位异或（^）：对应位不同结果为1，相同为0。Pascal中的`xor`。 5. 左移位（<<）：将二进制数向左移动指定位数，相当于乘以2的幂次。Pascal中是`shl`。 6. 右移位（>>）：向右移动指定位数，相当于除以2的幂次。在Pascal中是`shr`。 位运算的优先级是：not > and > xor > or。这些运算符可以用来进行高效的位操作，例如： - 使用`x & -x`可以找出一个数二进制表示中的最后一个1，这是获取低bit的常见方法。 - 通过`a = a | b`可以将b的所有位设置到a中。 - 不使用中间变量交换两个数的技巧是：`a = a ^ b; b = b ^ a; a = a ^ b;`。 - `~0u`等于`4294967295`，即2的32次方减1，在无符号整数中表示所有位都为1。 作为引例，我们考虑一个n×n的棋盘（n≤20）放置n个车（车可以在同一行或同一列上移动）的问题。如果要求这些车不能互相攻击，我们可以使用状态压缩递推（States Compressing Recursion, SCR）来解决。每放置一个车，我们就可以排除掉该行和该列的其他车的可能性，通过位运算更新当前的可行状态。例如，对于第i行放置车，我们可以用一个二进制数表示哪些行已经放置了车，然后通过位运算排除掉第i行。 这种问题的解决思路是，对于每一行，我们都有n种可能的选择，第一行有n种，第二行有n-1种，以此类推，最后一行只有1种。但通过状态压缩，我们可以避免直接计算组合数，而是使用位运算动态维护可行状态，从而实现更快速的求解过程。 状态压缩是一种强大的工具，它通过高效地编码和处理状态，显著减少了空间复杂性，对于处理大规模状态问题尤其有用。在信息学竞赛和实际编程中，掌握状态压缩和位运算技巧能帮助我们解决许多复杂问题。"