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

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

理解发生了什么的关键是要知道

BITSPERWORD

= 2

SHIFT

。因此，

x[i>>SHIFT]

找到数组的哪个32位元素

x

具有与对应的位

i

。（通过

i

向右移动5位，您只需将其除以32。）找到的正确元素后

x

，

i

可以使用的低5位查找

x[i>>SHIFT]

对应于的哪个特定位

i

。那是什么

i& MASK

？通过将1移位该位数，可以将与1对应的位移动

x[i>>SHIFT]

到与中

i

第th个位相对应的确切位置

x

。

这里有更多的解释：

想象一下，我们需要

N

位向量中的位容量。由于每个

int

持有32位，我们将需要

(N + 31) / 32

int

用于存储的值（即，N /
32向上舍入）。在每个

int

值内，我们将采用以下约定：位从最低有效位到最高有效位排序。我们还将采用以下约定：向量的前32位在中

x[0]

，后32位在中

x[1]

，依此类推。这是我们正在使用的内存布局（在我们的位向量中显示与内存的每个位相对应的位索引）：

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

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

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

（我们可以为动态扩展此存储做准备，但这只会增加解释的复杂性。）

现在，假设我们要访问位

i

（对其进行设置，清除或仅了解其当前值）。我们需要首先弄清楚

x

要使用哪个元素。由于每个

int

值有32位，因此很容易：

subscript for x = i / 32

利用枚举常量，

x

我们想要的元素是：

x[i >> SHIFT]

（将其看作是进入N位向量的32位宽窗口）。现在，我们必须找到与相对应的特定位

i

。从内存布局来看，不难发现窗口中的第一个（最右边）位对应于bit
index

32 * (i >> SHIFT)

。（窗口在中的

i >>SHIFT

插槽之后开始

x

，每个插槽都有32位。）由于那是窗口中的第一位（位置0），因此我们感兴趣的位在位置

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

在窗户上。经过一些试验，您可以使自己确信该表达式始终等于

i % 32

（实际上，这是mod运算符的一个定义），而该表达式又始终等于

i &MASK

。由于最后一个表达式是计算我们想要的最快方法，因此我们将使用它。

从这里开始，其余的工作非常简单。我们从窗口最低有效位置（即常量

1

）中的单个位开始，然后将其向左移动

i &MASK

一位

i

，以使其到达窗口中与位向量中的位相对应的位置。这是表达的地方

1 << (i & MASK)

来自。现在将钻头移到我们想要的位置，我们可以将其用作设置，清除或查询该位置上的钻头值的掩码，

x[i>>SHIFT]

并且我们知道实际上是在设置，清除或查询该值位

i

在我们的位向量。