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

小编典典

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

algorithm

在《编程珍珠》（第2版）的第140页上，乔恩提出了一种使用位向量的集合的实现。

现在我们来看两个最终的结构，它们利用我们的集合表示整数这一事实。位向量是列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 & MASKi的低5位，而i>>SHIFT将i向右移动5位。

有人会详细介绍这些算法吗？对我而言，位运算始终是一个神话，:(

阅读 247

2020-07-28

共1个答案

小编典典

理解发生了什么的关键是要知道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在我们的位向量。

2020-07-28