在编程珠玑位向量执行组，第2版 [英] bit vector implementation of set in Programming Pearls, 2nd Edition
问题描述
在第140编程珍珠，第二版，乔恩提出了套有位向量的实现。
现在，我们将转向到利用的事实，我们重新集合present整数最后两个结构。位向量是一个老朋友从第1列。这是他们的私有数据和函数：
枚举{BITSPERWORD = 32，SHIFT = 5，MASK =为0x1F};
INT N，喜，* X;
空隙集（int i）以{×〔I＆GT;＆GT; SHIFT] | =（1＆其中;≤（I和MASK））; }
空隙CLR（int i）以{×〔I＆GT;＆GT; SHIFT]安培; =〜（1＆其中;≤（I和MASK））; }
INT试验（int i）以{返回×〔I＆GT;＆GT; SHIFT]安培; =（1＆其中;≤（I和MASK））; }
正如我聚集，比特向量的中心思想重新present一个整数集，如在第1列中描述，是第i个位被接通，当且仅当整数i是在集。
不过我真的很茫然，在涉及上述三种功能的算法。而本书没有给出解释。
我只能拿到 I和MASK 是获得低5位的我，而 I＆GT;＆GT;移是将我5位向右
有人会更多地讨论这些算法？位操作似乎总是一个神话对我来说，（
的关键是理解发生了什么事情是要认识到 BITSPERWORD = 2 SHIFT 。因此， X [I＆GT;＆GT; SHIFT] 发现该阵列的32位元素 X 有位对应的以我。 （通过移动我 5位，您只需32分右）一旦你找到了 X ，低5位可以用来找到我。这就是 I和MASK 做;通过移位1由该比特数，则内移动相应于1的确切位置的位×〔I＆GT;＆GT; SHIFT] 对应于我 日在 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 |
+ ---- + ---- + ------- + ---- + ---- + ---- +
等等
我们的第一步是分配所需的存储容量：
X =新INT [（N + BITSPERWORD - 1）＆GT;＆GT;转移]
（我们可以作出规定，动态扩展此存储，但是这只会增加复杂性的解释。）
现在假设我们想访问位我（要么设置，清除它，或者只是知道它的当前值）。我们首先需要弄清楚的其中元素x 来使用。由于每个32位 INT 的价值，这是简单的：
下标为X = 1/32
利用枚举常量时， X 我们想要的元素是：
X [I＆GT;＆GT;转移]
（想想这是一个32位宽的窗户进入我们的N位向量）。现在，我们必须要找到特定位对应我。纵观内存布局，它不是很难搞清楚，在窗口的第一个（最右边）位对应位指数 32 *（I＆GT;＆GT; SHIFT）。 （后窗口启动I＆GT;＆GT;移插槽 X ，并且每个插槽为32位。）由于这是在窗口（位置0）的第一位，然后我们感兴趣的是位在位置
我 - （32 *（I＆GT;＆GT; SHIFT））
在窗口。随着一个小实验，你能说服自己，这EX pression总是等于 I％32 （实际上，这就是MOD操作符的一个定义），在反过来，总是等于 I和MASK 。由于这最后的EX pression是计算我们想要的最快的方式，这就是我们将使用什么。
从这里开始，剩下的就是pretty的简单。我们先在窗口的最不显著位置（也就是常 1 ）单个位，并将其移动到左边 I和MASK 位得到它的位置对应于位我的位向量的窗口。这是前pression
1＆LT;＆LT; （I和MASK）
从何而来。随着位，现在搬到了我们所希望的，我们可以用这个作为一个掩码设置，清除或查询该位在该位置的值 X [I＆GT;＆GT; SHIFT] ，我们知道，我们实际上是在设置，清除，或查询位的值我在我们的位向量。
On Page 140 of Programming Pearls, 2nd Edition, Jon proposed an implementation of sets with bit vectors.
We'll turn now to two final structures that exploit the fact that our sets represent integers. Bit vectors are an old friend from Column 1. Here are their private data and functions:
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)); }
As I gathered, the central idea of a bit vector to represent an integer set, as described in Column 1, is that the i-th bit is turned on if and only if the integer i is in the set.
But I am really at a loss at the algorithms involved in the above three functions. And the book doesn't give an explanation.
I can only get that i & MASK is to get the lower 5 bits of i, while i>>SHIFT is to move i 5 bits toward the right.
Anybody would elaborate more on these algorithms? Bit operations always seem a myth to me, :(
The key to understanding what's going on is to recognize that BITSPERWORD = 2SHIFT. Thus, x[i>>SHIFT] finds which 32-bit element of the array x has the bit corresponding to i. (By shifting i 5 bits to the right, you're simply dividing by 32.) Once you have located the correct element of x, the lower 5 bits of i can then be used to find which particular bit of x[i>>SHIFT] corresponds to i. That's what i & MASK does; by shifting 1 by that number of bits, you move the bit corresponding to 1 to the exact position within x[i>>SHIFT] that corresponds to the ith bit in x.
Here's a bit more of an explanation:
Imagine that we want capacity for N bits in our bit vector. Since each int holds 32 bits, we will need (N + 31) / 32 int values for our storage (that is, N/32 rounded up). Within each int value, we will adopt the convention that bits are ordered from least significant to most significant. We will also adopt the convention that the first 32 bits of our vector are in x[0], the next 32 bits are in x[1], and so forth. Here's the memory layout we are using (showing the bit index in our bit vector corresponding to each bit of memory):
+----+----+-------+----+----+----+
x[0]: | 31 | 30 | . . . | 02 | 01 | 00 |
+----+----+-------+----+----+----+
x[1]: | 63 | 62 | . . . | 34 | 33 | 32 |
+----+----+-------+----+----+----+
etc.
Our first step is to allocate the necessary storage capacity:
x = new int[(N + BITSPERWORD - 1) >> SHIFT]
(We could make provision for dynamically expanding this storage, but that would just add complexity to the explanation.)
Now suppose we want to access bit i (either to set it, clear it, or just to know its current value). We need to first figure out which element of x to use. Since there are 32 bits per int value, this is easy:
subscript for x = i / 32
Making use of the enum constants, the x element we want is:
x[i >> SHIFT]
(Think of this as a 32-bit-wide window into our N-bit vector.) Now we have to find the specific bit corresponding to i. Looking at the memory layout, it's not hard to figure out that the first (rightmost) bit in the window corresponds to bit index 32 * (i >> SHIFT). (The window starts afteri >> SHIFT slots in x, and each slot has 32 bits.) Since that's the first bit in the window (position 0), then the bit we're interested in is is at position
i - (32 * (i >> SHIFT))
in the windows. With a little experimenting, you can convince yourself that this expression is always equal to i % 32 (actually, that's one definition of the mod operator) which, in turn, is always equal to i & MASK. Since this last expression is the fastest way to calculate what we want, that's what we'll use.
From here, the rest is pretty simple. We start with a single bit in the least-significant position of the window (that is, the constant 1), and move it to the left by i & MASK bits to get it to the position in the window corresponding to bit i in the bit vector. This is where the expression
1 << (i & MASK)
comes from. With the bit now moved to where we want it, we can use this as a mask to set, clear, or query the value of the bit at that position in x[i>>SHIFT] and we know that we're actually setting, clearing, or querying the value of bit i in our bit vector.
这篇关于在编程珠玑位向量执行组，第2版的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
