algorithm - 《 Programming Pearls，第二版》中set的位矢量实现

Question

在第2版的programming pearls的140页上，jon提出了一种位向量集的实现。
现在我们将讨论最后两个利用集合表示整数这一事实的结构。位向量是第1列的老朋友。以下是它们的私有数据和功能：

enum { BITSPERWORD = 32, SHIFT = 5, MASK = 0x1F };
int n, hi, *x;
void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i)  {        x[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i) { return x[i>>SHIFT] &=  (1<<(i & MASK)); }

正如我收集到的，如第1列所述，表示整数集的位向量的中心思想是，当且仅当整数i在集合中时，才打开第i位。
但我真的对上述三个函数所涉及的算法感到茫然。这本书也没有给出解释。
我只能得到 i & MASK是为了得到较低的5位i，而 i>>SHIFT是为了向右移动5位i。
有人会详细说明这些算法吗？比特操作在我看来总是一个神话：（

Answer 1

了解情况的关键是要认识到BITSPERWORD=2SHIFT。因此，x[i>>SHIFT]查找数组中哪个32位元素的位对应于x。（通过向右移动i5位，您只需除以32即可。）一旦找到i的正确元素，x的较低5位便可用于查找i的哪个特定位对应于x[i>>SHIFT]。这就是i所做的；通过将1移这个位数，您将对应于1的位移到i & MASK内对应于x[i>>SHIFT]中第i位的精确位置。
这里有更多的解释：
假设我们需要位向量中x位的容量。由于每个N包含32位，我们需要存储int(N + 31) / 32值（即n/32向上取整）。在每个int值中，我们将采用从最低有效位到最高有效位的顺序的约定。我们还将采用这样的约定：向量的前32位在int中，后32位在x[0]中，以此类推。下面是我们正在使用的内存布局（显示与每个内存位对应的位向量中的位索引）：

      +----+----+-------+----+----+----+
x[0]: | 31 | 30 | . . . | 02 | 01 | 00 |
      +----+----+-------+----+----+----+
x[1]: | 63 | 62 | . . . | 34 | 33 | 32 |
      +----+----+-------+----+----+----+
        etc.

我们的第一步是分配必要的存储容量：

x = new int[(N + BITSPERWORD - 1) >> SHIFT]

（我们可以为动态扩展这个存储提供条件，但这会增加解释的复杂性。）
现在假设我们想要访问位 x[1]（要么设置它，要么清除它，要么只知道它的当前值）。我们需要首先确定要使用 i的哪个元素。由于每个 x值有32位，这很容易：

subscript for x = i / 32

利用枚举常量，我们需要的 int元素是：

x[i >> SHIFT]

（把它看作是一个32位宽的窗口，可以看到n位向量）现在我们必须找到对应于 x的特定位。查看内存布局，不难发现窗口中的第一个（最右边的）位对应于位索引 i。（窗口在 32 * (i >> SHIFT)中的 i >> SHIFT插槽之后开始，每个插槽有32位。）因为这是窗口中的第一位（位置0），所以我们感兴趣的位在位置

i - (32 * (i >> SHIFT))

在窗户里。通过一些实验，您可以说服自己，这个表达式总是等于 x（实际上，这是mod运算符的一个定义），而mod运算符又总是等于 i % 32。因为最后一个表达式是计算我们想要什么的最快方法，所以我们将使用它。
从这里开始，剩下的就很简单了。我们从窗口最低有效位置（即常数 i & MASK）的一个位开始，向左移动 1位，将其移动到窗口中与位向量中的位 i & MASK相对应的位置。这就是表达

1 << (i & MASK)

来自。现在位移到我们想要的位置，我们可以用它作为一个掩码来设置、清除或查询位在 i中那个位置的值，我们知道我们实际上是在设置、清除或查询位向量中的位 x[i>>SHIFT]的值。