一个设置、清除和测试单个位的算法解释

Question

嘿，在《编程珠玑》这本书中，有一份源代码用于在实际上是一个集合表示的整数数组中设置、清除和测试给定索引位的位。

代码如下：

#include<stdio.h>
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1+ N/BITSPERWORD];

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

void clr(int i)
{
    a[i>>SHIFT] &= ~(1<<(i & MASK));
}

int test(int i)
{
    a[i>>SHIFT] & (1<<(i & MASK));
}

请问有人能为我解释一下SHIFT和MASK定义的原因吗？它们在代码中的目的是什么？

我已经阅读了之前相关的问题。

- jaircazarin

Answer 1

VonC发表了一篇关于位掩码的好回答。以下是更加具体于您发布的代码的信息。

给定表示位的整数，我们确定哪个数组成员保存该位。也就是说：位0到31存储在a[0]中，位32到63存储在a[1]中，依此类推。i>>SHIFT所做的全部工作就是i / 32。这可以确定位所在的a的成员。在使用优化编译器时，这两者可能是等效的。

显然，现在我们已经找到了位标志所在的a的成员，我们需要确保在该整数中设置正确的位。这就是1<

- Roger Lipscombe

Answer 2

从这里（为启动该主题提供的通用答案）

位掩码是一个值（可能存储在变量中），它使您能够隔离整数类型中的特定一组位。

通常，掩码将具有您感兴趣的位设置为1，并将所有其他位设置为0。然后，掩码允许您隔离位的值，清除所有位或设置所有位或将新值设置为位。

掩码（特别是多位掩码）通常具有相应的移位值，即需要左移的位数，以便最不重要的掩码位被移动到类型中最不重要的位。

例如，使用16位短数据类型，假设您想要能够屏蔽3、4和5位（LSB是编号0）。您的掩码和移位看起来可能是这样的：

#define MASK 0x0038
#define SHIFT 3

掩码通常以十六进制分配，因为在该基础上使用位数据类型更容易处理比十进制更为方便。历史上也曾经使用过八进制作为位掩码。

如果我有一个包含与掩码相关的数据的变量var，那么我可以像这样隔离位：

var & MASK

我可以这样单独分离所有其他位运算：

var & ~MASK

我可以这样清除位：

我可以这样清除位：

var &= ~MASK;

我可以这样清除其他位：

var &= MASK;

我可以这样设置所有的位。

var |= MASK;

我可以这样设置其他所有位

var |= ~MASK;

我可以这样提取位的十进制值

(var & MASK) >> SHIFT

我可以像这样为位分配一个新值。

var &= ~MASK;
var |= (newValue << SHIFT) & MASK;

- VonC

Answer 3

当您想在数组中设置一个位时，您需要执行以下操作：

1. 定位到正确的数组索引
2. 在该数组项内设置适当的位。

每个数组项中有32个位（BITSPERWORD=32），这意味着索引i必须分为两部分：

• 右侧的5位用作数组项中的索引
• 其余位（最左侧的28位）用作数组的索引。

您可以获得：

• 通过丢弃最右侧的五个位数来获取最左侧的28位，这正是i>>SHIFT所做的。
• 通过屏蔽除最右侧的五个位以外的所有内容来获取最右侧的五个位数，这就是i & MASK所做的。

我想您已经理解了其余部分。

- zoul

Answer 4

位运算和掩码的前几段是简明扼要的解释，并包含一些进一步学习的指针。

将8位字节视为来自8个成员宇宙的元素集。当相应的位被设置时，成员在集合中。多次设置一个位不会修改集合成员资格（一个位只能有2种状态）。C中的位运算符通过掩码和移位提供对位的访问。

- gimel

Answer 5

这段代码试图通过一个数组来存储N位，其中数组的每个元素包含BITSPERWORD（32）位。

因此，如果您要访问位i，则需要计算存储它的数组元素的索引（i/32），这就是i>>SHIFT所做的事情。

然后，您需要访问刚刚获取的数组元素中的那个位。

(i & MASK)给出了数组元素（字）中的位位置。 (1<<(i & MASK))使该位置上的位被设置。

现在，您可以通过(1<<i & MASK))在a[i>>SHIFT]中设置/清除/测试该位。

您还可以认为i是一个32位数字，其中位6~31表示存储它的数组元素的索引，位0~5表示字中的位位置。

- ting