BoP——1.2将帅问题

在存储空间限制的情况下如何存储数据

问题很简单，就是在中国象棋棋盘上，当只剩下将和帅的时候，问将帅有多少中可能的所处位置。但是要求代码中只能使用一个字节存储变量。
（将帅不能碰头，也就是说将帅不能处于同一条直线上）

将帅问题

处理也很简单，将帅所能移动的位置有限，局限在一个3*3的空间中，如果将每个位置标号：

位置标号

两方都用这样的形式表示。那么只需要两个嵌套的循环，从1-9,一次进行遍历，i%3 != j%3就是一种可能性。

时间复杂度O（N^2）无疑，需要遍历。
但是代码中只能有一个字节存储变量，也就是说只能有一个额外的变量。

一个字节8个bit，能表示256个数。但是不能拆成两个来表示。因此我们需要一种手段能够使用一个变量表示两个变量。
这个变量只能是个char了

方法一：借助位操作。

我们将8bit的变量，分成两部分，前4bit表示一个数，后4bit表示另一个数。这样能表示的范围就是0-15,足够表示出9。

位操作

&：与操作，两者都为1，结果才为1，能够将某些位，置为0。还能保持1的位置不变
|：或操作，两位都是0是才为0，能够判断0的位置。
^：异或操作，两位相同时为0,否则为1，连个相同的数疑惑值为0
另外还有取反和左右移。

我们可以使用这个char的高位和低位存储两个不同的数。然后通过左右移，和与操作，来获取这两个数，例如

char i=123;
i>>4;//取得高四位的值：右移四位，将高四位移动到第四位，高四位0填充。
255>>4;//获得00001111,掩码
i&(255>>4)//这样可以获取低四位

如何设置固定的值？可以将固定的位清空，然后与上固定的数值，就能构造出来

(i&(255>>4))&(n<<4);//先将固定的位清空，然后于上固定的数值，因为是 高4位，所以固定的数值也要左移四位。
(i&(255<<4))&n;//低四位设置固定的值。

这样就没啥问题了。两个书都能表示出来了。接下来只需要将这些位操作做成宏，写出循环就行了。

方法二：位域

参考文章

通俗理解就是控制一个变量所占位数。

struct{
  char l:4;
  char r:4;
}

结束！这样就把一个8位，分成了两个4位。问题就解决了。

方法三：

说不上来的一种思想

char i = 81;
while(i--)
{
  if(i/9%3 != i%9%3)
  {
   //一种结果
  }
}

但是想想确实可以。