[数据结构与算法]邓俊辉《数据结构C++》第二章课后习题中位图Bitmap的三个接口实现代码解释

void set(int i); //将第i位置为true（将整数i加入当前集合）
void clear(int i); //将第i位置为false（从当前集合中删除整数i）
bool test(int i); //测试第i位是否为true（判断整数i是否属于当前集合）

教材给的实现代码如下：

void set(int k) { expand(k); M[k >> 3] |= (0x80 >> (k & 0x07)); }
void clear(int k) { expand(k); M[k >> 3] &= ~(0x80 >> (k & 0x07)); }
bool test(int k) { expand(k); return M[k >> 3] & (0x80 >> (k & 0x07)); }

邓公使用字符数组实现位图。即char* M。
首先，位图的每一bit表示一个数。M[0]表示第0-7位，M[1]表示第8-15位…以此类推。
比如，整个位图是这样的：00001010 01000100 1001100… 表示第4位，6位，9位，13位，16位，19位，20位在位图中（存在就是此为位为1），也就是在集合中。而0表示不存在。如第0位，第1位，第2位，第3位，第5位均不在。注意第一个bit位是第0位，不是第1位。同样，前8位是M[0],不是M[1]。
如果我想把18加到位图中，只需要第18位变为1。即M[2]的第3位。此时序列变为00001010 01000100 1011100…。发现18/8=2---->变化发生在M[2]。余数为2---->变化发生在M[2]的第3位。
同理，如果我想再把11加到位图中，只需要第11位变为1。即M[1]的第4位。此时序列变为00001010 01010100 1011100…。发现11/8=1---->变化发生在M[1]。余数为3---->变化发生在M[1]的第4位。
接下来就可以分析代码了。
M[k >> 3] |= (0x80 >> (k & 0x07))----->M[k >> 3] =M[k >> 3] | (0x80 >> (k & 0x07))
我们假设k=108，按照上述分析，不难推出：
发现108/8=13---->变化发生在M[13]。余数为4---->变化发生在M[13]的第5位。注意M[13]前面有13个byte（M[0]-M[12]），13*8=104bit，M[13]的第5位前面有104+4=108个bit（0-107bit），k是第109个比特位，但是却是第108位。
k=108的对应二进制数为1101100，
k >> 3表示将k的二进制数向右移动三位得到0001101，此为13，（即k÷8=13）。
0x07表示16进制数7，对应二进制数为00000111。k & 0x07----->1101100&00000111=00000100，所以k & 0x07表示只保留k的最后三个二进制数位。其实，这个最后三个二进制数位表示的数就是k÷8的余数。在这里这个数为00000100，即为4。（k%8=4）
0x80表示16进制数128，对应二进制数为10000000，0x80 >> (k & 0x07))表示10000000向右移动4位得到00001000 。
所以，M[k >> 3] | (0x80 >> (k & 0x07))------->M[13]|(00001000).注意M[13]可能有255种不同情况。因为我们并不知道104-111是否在集合中，也就是不确定对应为是1还是0。我们随意取一种情况。假设M[13]是这样的：01000011.那么M[13] | (00001000)----->：01000011 | 00001000---->01001011。
至此，我们成功将整数108加入到了集合中，即将第108位置为true。
下面的void clear(int i)和bool test(int i)可同理分析，不必赘述。