编程珍珠,第2版中的位向量实现

Question

在编程珍珠,第2版的第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 & MASKi的低5位,而i>>SHIFT向右移动i 5位.

有人会详细说明这些算法吗？位操作对我来说似乎总是神话,:(

Answer 1

比特场和你

我将用一个简单的例子来解释基础知识.假设您有一个带有四位的无符号整数:

[0][0][0][0] = 0

您可以通过将其转换为基数2来表示0到15之间的任何数字.假设我们的右端是最小的:

[0][1][0][1] = 5

所以第一位加总1,第二位加2,第三位加4,第四位加8.例如,这里是8:

[1][0][0][0] = 8

所以呢？ 假设您要在应用程序中表示二进制状态 - 如果启用了某个选项,是否应绘制某个元素,依此类推.您可能不希望为每一个使用整数 - 它使用32位整数来存储一位信息.或者,以四位继续我们的示例:

[0][0][0][1] = 1 = ON
[0][0][0][0] = 0 = OFF //what a huge waste of space!

(当然,问题在现实生活中更为明显,因为32位整数看起来像这样:

[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0] = 0

答案是使用位字段.我们有一组属性(通常是相关的),我们将使用位操作来打开和关闭.因此,比如说,您可能在要打开或关闭的硬件上有4种不同的灯.

 3  2  1  0
[0][0][0][0] = 0

(为什么我们从light 0开始？我会在一秒钟内解释一下.)注意这是一个整数,并存储为整数,但用于表示多个对象的多个状态.疯!假设我们打开灯2和1:

 3  2  1  0
[0][1][1][0] = 6

在这里你应该注意的重要事项:可能没有明显的理由说明灯2和灯1应该等于6,并且我们如何对这种信息存储方案做任何事情可能并不明显.如果添加更多位,它看起来并不明显:

 3  2  1  0
[1][1][1][0] = 0xE \\what?

我们为什么关心这个？对于0到15之间的每个数字,我们只有一个状态吗？如果没有一些疯狂的一系列switch语句,我们将如何管理它？啊...

最后的光

因此,如果您之前使用过二进制算术,您可能会发现左侧数字与右侧数字之间的关系当然是基数2.即:

1*(2 ³)+ 1*(2 ²)+ 1*(2 ¹)+0*(2 ⁰)= 0xE

因此,每个光存在于等式的每个项的指数中.如果指示灯亮,则其术语旁边有一个1 - 如果指示灯熄灭,则表示零.花点时间说服自己在0到15之间只有一个整数对应于此编号方案中的每个状态.

位操作符

现在我们已经完成了这个,让我们花点时间看一下这个设置中的bithifting对整数的影响.

[0][0][0][1] = 1

当您将位向左或向右移位整数时,它会逐字地移动这些位.(注意:我100%否定这个负数的解释!有龙!)

1<<2 = 4
[0][1][0][0] = 4
4>>1 = 2
[0][0][1][0] = 2

当移位用多个位表示的数字时,您将遇到类似的行为.另外,要说服自己x >> 0或x << 0只是x,应该不难.不会转移到任何地方.

这可能解释了Shift操作符对任何不熟悉它们的人的命名方案.

按位运算

这种二进制数字的表示也可以用来阐明整数上按位运算符的运算.第一个数字中的每个位都是xor-ed,-ed或or-ed及其对应的数字.花一点时间冒险到维基百科并熟悉这些布尔运算符的功能 - 我将解释它们如何在数字上起作用,但我不想详细地重述一般的想法.

...

欢迎回来!让我们首先检查OR(|)运算符对两个整数的影响,存储在四位中.

 OR OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [1][1][0][1] = 0xD

强硬!这与布尔OR运算符的真值表非常相似.请注意,每列忽略相邻的列,只需在结果列中填入第一位和第二位的结果.另请注意,在该特定列中,任何或1的值为1.任何或零的东西都是一样的.

AND(&)的表很有意思,虽然有点倒置:

 AND OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [1][0][0][0] = 0x8

在这种情况下,我们做同样的事情 - 我们对列中的每个位执行AND运算,并将结果放在该位中.没有专栏关心任何其他专栏.

关于这一点的重要教训,我邀请您使用上图验证:任何与零编号的AND-ed为零.此外,同样重要的是 - 与一个AND编号的数字没有任何关系.他们保持不变.

最后一张表,XOR,有一些行为,我希望你们现在都能找到它们.

 XOR OPERATOR ON:
 [1][0][0][1] = 0x9
 [1][1][0][0] = 0xC
________________
 [0][1][0][1] = 0x5

每个位都与其列yadda yadda进行异或,依此类推.但仔细看第一行和第二行.哪些位改变了？(其中一半.)哪些位保持不变？(没有回答这个问题的要点.)

如果(并且仅当)第二行中的位为1,则第一行中的位将在结果中更改!

一个灯泡的例子!

所以现在我们有一套有趣的工具可以用来翻转各个位.让我们回到灯泡示例,只关注第一个灯泡.

 0
[?] \\We don't know if it's one or zero while coding

我们知道我们有一个操作总能使这个位等于一个OR 1运算符.

0|1 = 1
1|1 = 1

因此,忽略其余的灯泡,我们可以做到这一点

4_bit_lightbulb_integer | = 1;

并且确定我们没有做任何事情,只是将第一个灯泡设置为ON.

 3  2  1  0
[0][0][0][?] = 0 or 1? \\4_bit_lightbulb_integer
[0][0][0][1] = 1
________________
[0][0][0][1] = 0x1

同样,我们可以将数字与零一致.好吧 - 不是很零 - 我们不想影响其他位的状态,所以我们将用它们填充它们.

我将使用一元(单参数)运算符进行位否定.〜(NOT)按位运算符翻转其参数中的所有位.〜(0X1):

[0][0][0][1] = 0x1
________________
[1][1][1][0] = 0xE

我们将结合下面的AND位使用它.

我们来做4_bit_lightbulb_integer&0xE

 3  2  1  0
[0][1][0][?] = 4 or 5? \\4_bit_lightbulb_integer
[1][1][1][0] = 0xE
________________
[0][1][0][0] = 0x4

我们在右侧看到很多整数,这些整数没有任何直接相关性.如果你经常处理位字段,你应该习惯这个.看左边.右侧的位始终为零,其他位不变.我们可以关掉灯0并忽略其他一切!

最后,您可以使用XOR位有选择地翻转第一位!

 3  2  1  0
[0][1][0][?] = 4 or 5? \\4_bit_lightbulb_integer
[0][0][0][1] = 0x1
________________
[0][1][0][*] = 4 or 5?

我们实际上并不知道*现在的价值是什么 - 只是从那些翻转过来的？是.

结合位移和按位运算

关于这两个操作的有趣事实是,当它们结合在一起时,它们允许您操作选择性位.

[0][0][0][1] = 1 = 1<<0
[0][0][1][0] = 2 = 1<<1
[0][1][0][0] = 4 = 1<<2
[1][0][0][0] = 8 = 1<<3

嗯.有趣.我将在这里提到否定运算符(〜),因为它以类似的方式用于为位字段中的AND运算产生所需的位值.

[1][1][1][0] = 0xE = ~(1<<0)
[1][1][0][1] = 0xD = ~(1<<1)
[1][0][1][1] = 0xB = ~(1<<2)
[0][1][1][1] = 0X7 = ~(1<<3)

您是否看到移位值与移位位的相应灯泡位置之间存在有趣的关系？

规范的bithift运算符

如上所述,我们有一个有趣的,通用的方法,用上面的位移位器打开和关闭特定的灯.

要打开灯泡,我们使用位移生成1在正确的位置,然后将其与当前灯泡位置进行OR运算.假设我们想打开灯3,而忽略其他一切.我们需要进行OR运算

 3  2  1  0
[?][?][?][?]  \\all we know about these values at compile time is where they are!

和0x8

[1][0][0][0] = 0x8

由于位移,这很容易!我们将选择灯的数量并将值切换为:

1<<3 = 0x8

然后:

4_bit_lightbulb_integer |= 0x8;

 3  2  1  0
[1][?][?][?]  \\the ? marks have not changed!

我们可以保证第三个灯泡的位设置为1,并且没有其他任何改变.

清除有点类似 - 我们将使用上面的否定位表,例如,清除光2.

~(1<<2) = 0xB = [1][0][1][1]

4_bit_lightbulb_integer&0xB:

 3  2  1  0
[?][?][?][?] 
[1][0][1][1]
____________
[?][0][?][?]

翻转位的XOR方法与OR方法相同.

所以比特切换的规范方法是这样的:

打开灯我:

4_bit_lightbulb_integer|=(1<<i)

关掉灯我:

4_bit_lightbulb_integer&=~(1<<i)

翻转灯我:

4_bit_lightbulb_integer^=(1<<i)

等等,我怎么读这些？

为了检查一下,我们可以简单地将所有位清零,除了我们关心的位.然后我们将检查结果值是否大于零 - 因为这是唯一可能非零的值,当且仅当它非零时,它将使整个整数非零.例如,要检查第2位:

1 << 2:

[0][1][0][0]

4_bit_lightbulb_integer:

[?][?][?][?]

1 << 2&4_bit_lightbulb_integer:

[0][?][0][0]

记得从前面的例子中得出的值是多少？没改变.还记得任何AND 0都是0.因此,我们可以肯定地说,如果该值大于零,则位置2处的开关为真且灯泡为零.同样,如果值为off,则整个事物的值将为零.

(你可以交替地将4_bit_lightbulb_integer的整个值移动i比特,并将它与1.一起移动.如果一个比另一个快,我不记得我的头顶但是我怀疑它.)

所以规范检查功能:

检查位i是否打开:

if (4_bit_lightbulb_integer & 1<<i) {
\\do whatever

}

具体细节

既然我们有一套完整的按位运算工具,我们可以在这里查看具体的例子.这基本上是相同的想法 - 除了更简洁和强大的执行方式.我们来看看这个函数:

void set(int i)  {        x[i>>SHIFT] |=  (1<<(i & MASK)); }

从规范的实现,我将猜测这是试图将一些位设置为1!让我们取一个整数,看看这里发生了什么,如果我将值0x32(十进制50)输入i:

x[0x32>>5] |= (1<<(0x32 & 0x1f))

好吧,那是一团糟......让我们在右边剖析这个操作.为方便起见,假装有24个不相关的零,因为它们都是32位整数.

...[0][0][0][1][1][1][1][1] = 0x1F
...[0][0][1][1][0][0][1][0] = 0x32
________________________
...[0][0][0][1][0][0][1][0] = 0x12

看起来在顶部的边界处切断了一切,其中1s变为零.这种技术称为比特掩蔽.有趣的是,这里的边界将结果值限制在0到31之间......这正是我们对32位整数的位位置数!

x [0x32 >> 5] | =(1 <<(0x12))让我们看另一半.

...[0][0][1][1][0][0][1][0] = 0x32

向右移五位:

...[0][0][0][0][0][0][0][1] = 0x01

请注意,此转换完全破坏了函数第一部分的所有信息 - 我们有32-5 = 27个剩余位,这些位可能是非零的.这表示选择了整数数组中的2 ^27个整数中的哪一个.所以简化的等式现在是:

x[1] |= (1<<0x12)

这看起来像规范的位设置操作!我们刚刚选择了

因此,我们的想法是使用前27位来选择要移位的整数,最后5位指示要移位的整数中的32位.

Answer 2

理解正在发生的事情的关键是识别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^第在位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.查看内存布局,不难发现窗口中的第一个(最右边)位对应于位索引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在我们的位向量.