猫史档案馆

状态压缩初步

其实也压缩不了多大空间，纯属吃饱了撑的写的

使用情景：

    当你想要表示一位玩家的状态，如：玩家A有着 {疾跑，燃烧，喵} 的三种叠加效果，你是否是会使用类似一个数组的存法进行存储呢？

当使用状态压缩时，仅需要存储一个数字即可。

 

状态压缩是什么：

     常规操作：当状态只有是或否时，我们可以使用布尔值进行表示。

       而当多个状态构成了一个集合，一般会选择使用一个布尔值数组进行表示。状态压缩同样如此，只不过是使用了一个十进制数来表示二进制。

       如现有5个状态：{A,B,C,D,E}; 他们的布尔值分别是 {1,0,1,0,1}; 

       正常存法：使用数组 [1,0,1,0,1]; 空间复杂度：O(n)

       状态压缩存法：21 (0b10101); 空间复杂度：O(1)

       可见，状态压缩存法的空间复杂度会比使用数组存法大大减小

如何使用状态压缩：

       首先你必须十分熟悉位运算，这里不再赘述，可以自行百度优先搜索。

          假设现有状态压缩数 S 表示一个状态集合.

         

S = 0; // 所有状态都为false
S |= (1 << (n+1)) - 1 // 将前n位状态都设置为true
S &= ~((1 << (n+1)) - 1)  // 将前n位状态都设置为false
S |= 1 << n; // 将第n位的状态设置为true
S &= ~(1 << n); // 将第n位的状态设置为false
((S >> n) & 1) // S的第n位是否位true

// 以上是基础用法， 更多用法懒得写了

状态压缩的弊端：

     1. 必须给每个状态进行标号

       2. 难以动态调整各个状态的下标

       3. 可读性差

       4.  所使用的数字将会随着状态数的增大而指数级增大，如32个状态就有2亿大小了