读编程之美1.2——中国象棋将帅问题

初见这个题目，不知如何下手，容易将棋盘表示复杂化。题目中仅仅是要求判断将与帅是否照面，而将与帅只能在各自的9个位置移动，因而只需要形式化1~9这9个数字。只要想到1~9这个题目基本就解了，至于后面的位表示与位操作，属于基本的计算机程序设计的基础知识。

代码清单1-7值得拓展学习一下，其中用到了位域（bit-fields）的知识。

位域的概念《C程序设计语言》用了一页纸介绍，说明了应用场合主要是为了节省空间或直接访问位，应用场景如编译器的符号表以及一些硬件的驱动程序。我想做网络开发、信息编码压缩解压缩、位图等方面可能还会用到，其余的场景多半会去讨论怎么节省时间开销，让程序运行的更加高效。另外讨论了如此题的解法一中的常规解决手段，即是位操作。一般是定义一系列的掩码（masks）——可以用宏定义，或者枚举类型——来完成。谈及位域，举了如下的例子：

struct {
    unsigned int is_keyword: 1;
    unsigned int is_extern: 1;
    unsigned int is_static: 1;
} flags;

View Code

访问位的方法与普通的结构体变量类似，例如将is_extern比特位置1，即flags.is_extern = 1。需要注意的是位域涉及到字对齐的概念、存储方式的概念，这些因机器与实现的编译器而异。通常字对齐规则与普通的struct变量一样，用占用字节数最多的类型来对齐，例如下面的代码中对齐的基本类型是unsigned int，4字节，前两个成员能在4字节内表示，而最后一个成员length需要10比特，已经超出了4字节，那么就需要再申请4个字节，从头来存储，所以Entry结构一共会占用8个字节。另外如果成员length只需要2比特，但又想让强制从下4个字节开始，可以添加一个成员，占用比特数为0.

struct Entry {
    unsigned char significant: 1;
    unsigned int position: 24;
    unsigned int length: 10;
};

View Code

存储方式一般分大端与小端，通用PC小端多见。因为机器的的基本存储单元是字节，所以涉及到自定义类型时候，势必就会有存储顺序，是高字节在前还是低字节在前，解释不同，值就不同。小端格式一般是低字节存低地址，高字节存高地址，大端格式反之。位存储时候也是先声明的成员依次从低位像高位存，如果跨了字节，就以小端或者大端方式存。

此外还有一种位读写方式是STL库中提供的泛型类bitset，它支持对位赋值的操作，也支持整体的位运算，最方便的是输入输出流被重载，很容易查看对应的位是否被置正确。相比于位域，bitset不能支持局部几个比特位的访问，而这正是位域的优势。不过对将与帅的问题，要求一个字节，而bitset基本的对齐是4个字节，所以可能不符合题目要求，不过对于其它的位操作场合却是一种很好的选择。

读编程之美1.2——中国象棋将帅问题,布布扣,bubuko.com

读编程之美1.2——中国象棋将帅问题

原文：http://www.cnblogs.com/foreverinside/p/3579441.html