第一章 游戏之乐
1.2 中国象棋
该题本质上比较简单，但因为限制条件（只能使用1个字节），所以考察较深
- 解法1:将1个字节的8位分为前后4位，并定义二进制操作，对前后4位分别进行操作
- 解法2:使用位域，将一个字节直接分为前后四位，可以直接进行加减
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ChineseChess
{
unsigned char a : 4;
unsigned char b : 4;
} i;
int main(){
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);
}
}
}
return 0;
}
位域
参考：C语言位域（位段）详解
有些数据在存储时并不需要占用一个完整的字节，只需要占用一个或几个二进制位即可。例如开关只有通电和断电两种状态，用 0 和 1 表示足以，也就是用一个二进位。
正是基于这种考虑，C语言提供了一种叫做位域的数据结构。
在结构体定义时，我们可以指定某个成员变量所占用的二进制位数（Bit），这就是位域。
C语言标准规定，位域的宽度不能超过它所依附的数据类型的长度。通俗地讲，成员变量都是有类型的，这个类型限制了成员变量的最大长度，:后面的数字不能超过这个长度。
- unsigned int，长度为 4 个字节，共计 32 位
- unsigned char，长度为 1 个字节，共计 8 位
例子：
1
2
3
4
5
struct bs{
unsigned m;
unsigned n: 4;
unsigned char ch: 6;
};
:后面的数字用来限定成员变量占用的位数。- 成员 m 没有限制，根据数据类型即可推算出它占用 4 个字节（Byte）的内存。
- 成员 n、ch 被
:后面的数字限制，不能再根据数据类型计算长度，它们分别占用 4、6 位（Bit）的内存。
位域的存储规则：
- 当相邻成员的类型相同时，如果它们的位宽之和小于类型的 sizeof 大小，那么后面的成员紧邻前一个成员存储，直到不能容纳为止；如果它们的位宽之和大于类型的 sizeof 大小，那么后面的成员将从新的存储单元开始，其偏移量为类型大小的整数倍。
- 当相邻成员的类型不同时，不同的编译器有不同的实现方案，GCC 会压缩存储，而 VC/VS 不会
- 如果成员之间穿插着非位域成员，那么不会进行压缩
NOTE:
位域成员往往不占用完整的字节，有时候也不处于字节的开头位置，因此使用&获取位域成员的地址是没有意义的，C语言也禁止这样做。地址是字节（Byte）的编号，而不是位（Bit）的编号
无名位域:位域成员可以没有名称，只给出数据类型和位宽,一般用来作填充或者调整成员位置。因为没有名称，无名位域不能使用。
1.3 翻烙饼
经典题目，最朴素的想法是第一次将最大的饼想办法翻转到最下面，然后问题就缩减到n-1，再依次进行，最终问题的大小为需要进行的翻转次数为$2 * (n-1)$
可以以上述算法为上界，进行搜索，得到最优解，思考上界和下界的问题
第二章 数字之魅
2.1 二进制数中1的个数
经典题目 要注意数为负， 循环移位溢出等情况
- 解法1：每次去掉最右边的1，记录数量，知道数变为0
1
n = n & (n-1)
- 解法2:循环移位，每次判断是否为1
- 解法3:如果是8位二进制，可以将256个数建表，通过查表得到，时间复杂度位$O(1)$，牺牲了空间复杂度
2.2 阶乘
1. 阶乘末尾0的个数
末尾0必定是由10这个因数组成，而10又是由2和5组成，明显2会多于5，所以找有因数里多少个5即可
1
2
3
4
while(n){
count += n / 5; // 从最大的数开始计算其包含5的数量
n /= 5; // 减为1/5，中间没有5的倍数，直到n为0
}
2. 阶乘的2进制最低位1的位置
实质上是求阶乘中因数2的数量，可以按前面的思路
还可以根据规律，等于N - （N的二进制表示中1的数量）
2.3 寻找发帖水王
即找出超过1/2的元素，遍历数组元素，从第一个开始计数，如果计数n=0， 则将当前数作为候选水王，如果n>0，当前数与候选水王相同时，n=n+1,否则n=n-1
一次遍历即可得到
如果有3个，发帖数超过1/4，则设定3个候选水王，按上述规则进行遍历
第三章 结构之法
3.1 字符串移位包含问题
将源字符s复制为ss，另外可通过对比目标字符串长度进一步减少空间复杂度
3.2 电话号码对应的英语单词
1. 根据电话号码生成单词
对应生成即可，思考循环和递归两种方法
2. 根据电话号码，找一个有意义的单词
- 用1的方法，对每个生成单词查表
- 将字典中有意义的单词生成为号码字典，再根据号码去查单词（反向思维）
