1.2 中国象棋将帅问题
下过中国象棋的朋友都知道，双方的“将”和“帅”相隔遥远，并且不能照面。在象棋残局中，许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子（如图1-3所示）（为了下面叙述方便，我们约定用A表示“将”, B表示“帅”）。
图1-3 棋盘上的将和帅
A、B二子被限制在己方3×3的格子里运动。例如，在如上的表格里，A被正方形{d10,f10, d8, f8}包围，而B被正方形{d3, f3, d1, f1}包围。每一步，A、B分别可以横向或纵向移动一格，但不能沿对角线移动。另外，A不能面对B，也就是说，A和B不能处于同一纵向直线上（比如A在d10的位置，那么B就不能在d1、d2以及d3的位置上）。
请写出一个程序，输出A、B所有合法位置。要求在代码中只能使用一个字节存储变量。
分析与解法
问题本身并不复杂，只要把所有A、B互相排斥的条件列举出来就可以完成本题的要求。由于本题要求只能使用一个变量，所以首先必须想清楚在写代码的时候，有哪些信息需要存储，并且尽量高效率地存储信息。稍微思考一下，可以知道这个程序的大体框架是：
遍历A的位置
遍历B的位置
判断A、B的位置组合是否满足要求
如果满足，则输出
因此，需要存储的是A、B的位置信息，并且每次循环都要更新。首先创建一个逻辑坐标系统，一个可行的方法是用1~9的数字，按照行优先的顺序来表示每个格点的位置（如图1-4所示）。这样，只需要用模余运算就可以得到当前的列号，从而判断A、B是否互斥。
图1-4 用1~9的数字表示A、B的坐标
第二，题目要求只用一个变量，我们却要存储A和B两个子的位置信息，该怎么办呢？
可以先把已知变量类型列举一下，然后分析。
对于bool类型，估计没有办法做任何扩展了，因为它只能表示true和false两个值；而byte或int类型，它们能够表达的信息则更多。事实上，对本题来说，每个子都只需要9个数字就可以表示它的全部位置。
一个8位的byte类型能够表达28=256个值，所以用它来表示A、B的位置信息绰绰有余，因此可以把这个字节的变量（设为b）分成两部分。用前面的4 bit表示A的位置，用后面的4 bit表示B的位置，而4个bit可以表示16个数，这已经足够了。
问题在于：如何使用bit级的运算将数据从这一byte变量的左边和右边分别存入和读出。
下面是做法。
■ 将byte b（10100101）的右边4 bit（0101）设为n（0011）：
首先清除b右边的bits，同时保持左边的bits:
然后将上一步得到的结果与n做或运算：
■ 将byte b（10100101）左边的4 bit（1010）设为n（0011）：
首先，清除b左边的bits，同时保持右边的bits：
现在，把n移动到byte数据的左边：
n<<4=00110000
然后对以上两步得到的结果做或运算，从而得到最终结果。
■ 得到byte数据的右边4 bits或左边4 bits（e.g. 10100101中的1010以及0101）：
清除b左边的bits，同时保持右边的bits：
清除b右边的bits，同时保持左边的bits：
将结果右移4 bits：
10100000 >> 4=00001010
最后的挑战是如何在不声明其他变量约束的前提下创建一个for循环。可以重复利用1byte的存储单元，把它作为循环计数器并用前面提到的存取和读入技术进行操作。还可以用宏来抽象化代码，例如：
for (LSET(b, 1); LGET(b) <=GRIDW * GRIDW; LSET(b, (LGET(b)+1)))
解法一（如代码清单1-6所示）
代码清单1-6
#include <stdio.h>
#define HALF_BITS_LENGTH 4
// 这个值是记忆存储单元长度的一半，在这道题里是4bit
#define FULLMASK 255
// 这个数字表示一个全部bit的mask，在二进制表示中，它是11111111
#define LMASK (FULLMASK <<HALF_BITS_LENGTH)
// 这个宏表示左bits的mask，在二进制表示中，它是11110000
#define RMASK (FULLMASK >> HALF_BITS_LENGTH)
// 这个数字表示右bits的mask，在二进制表示中，它表示00001111
#define RSET(b, n) (b=((LMASK & b) | n)))
// 这个宏，将b的右边设置成n
#define LSET(b, n) (b=((RMASK & b) | ((n <<HALF_BITS_LENGTH)))
// 这个宏，将b的左边设置成n
#define RGET(b) (RMASK & b)
// 这个宏得到b的右边的值
#define LGET(b) ((LMASK & b) >> HALF_BITS_LENGTH)
// 这个宏得到b的左边的值
#define GRIDW 3
// 这个数字表示将帅移动范围的行宽度
int main()
{
unsigned char b;
for(LSET(b, 1); LGET(b) <=GRIDW * GRIDW; LSET(b, (LGET(b)+1)))
for(RSET(b, 1); RGET(b) <=GRIDW * GRIDW; RSET(b, (RGET(b)+1)))
if(LGET(b) % GRIDW !=RGET(b) % GRIDW)
printf("A=%d, B=%d\n", LGET(b), RGET(b));
return 0;
}
输出
格子的位置用N来表示，N=1, 2, …, 8, 9，依照行优先的顺序，如图1-5所示。
图1-5 格子的位置
考虑了这么多因素，总算得到了本题的一个解法，但是MSRA里却有人说，下面的一小段代码也能达到同样的目的。
BYTE i=81;
while(i--)
{
if(i / 9 % 3==i % 9 % 3)
continue;
printf(“A=%d, B=%d\n”, i / 9+1, i % 9+1);
}
很快又有另一个人说他的解法才是效率最高的（如代码清单1-7所示）。
代码清单1-7
struct {
unsigned char a:4;
unsigned char b:4;
} i;
for(i.a=1; i.a <=9; i.a++)
for(i.b=1; i.b <=9; i.b++)
if(i.a % 3 !=i.b % 3)
printf(“A=%d, B=%d\n”, i.a, i.b);
读者能自己证明一下吗？