解释用于设置，清除和测试单个位的算法
嘿，在Programming Pearls一书中，有一个源代码，用于在一个实际上是一组表示的整数数组中设置，清除和测试给定索引的一些内容。
代码如下：
#include #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<>SHIFT] &= ~(1<>SHIFT] & (1<<(i & MASK)); } 有人可以解释一下SHIFT和MASK定义的原因吗？ 他们在代码中的目的是什么？
我已经阅读了之前的相关问题 。
VonC总体上发布了一个关于位掩码的好答案。 以下是您发布的代码更具体的一些信息。
给定一个表示位的整数，我们计算出该位的哪个成员保存该位。 即：0到31位在a[0] ，位32到63位于a[1] ，等等。所有i>>SHIFT都是i / 32 。 这解决a该位的哪个成员。使用优化编译器，这些可能是等效的。
显然，现在我们已经发现了该位标志的哪个成员，我们需要确保在该整数中设置正确的位。 这就是1 << i所做的。 但是，我们需要确保不会尝试访问32位整数中的第33位，因此使用1 << (i & 0x1F)来限制移位操作。 这里的魔力是0x1F是31，所以我们永远不会将由i表示的位移位超过31个位置（否则它应该在a的下一个成员中移位）。
从这里 （获得此线程的一般答案）
位掩码是一个值（可以存储在变量中），使您可以隔离整数类型中的特定位集。
通常，屏蔽将您感兴趣的位设置为1，所有其他位设置为0.然后屏蔽允许您隔离位的值，清除所有位或设置所有位或设置新值比特。
掩码（特别是多位的）通常具有相关的移位值，该移位值是位需要向左移位的量，使得最低有效掩码位被移位到该类型中的最低有效位。
例如，使用16位短数据类型假设您希望能够屏蔽位3,4和5（LSB为数字0）。 你掩饰和转移看起来像
#define MASK 0x0038 #define SHIFT 3
掩码通常以hex分配，因为它更容易使用该基数中的数据类型的位而不是十进制。 历史上，八进制也用于位掩码。
如果我有一个变量var，它包含与掩码相关的数据，那么我可以像这样隔离这些位
var & MASK
我可以像这样隔离所有其他位
var & ~MASK
我可以清除这样的位
var &= ~MASK;
我可以像这样清除所有其他位
var &= MASK;
我可以像这样设置所有位
var |= MASK;
我可以像这样设置所有其他位
var |= ~MASK;
我可以像这样提取位的十进制值
(var & MASK) >> SHIFT
我可以为这些位分配一个新值
var &= ~MASK; var |= (newValue << SHIFT) & MASK;
当你想在数组中设置一个位时，你必须这样做
- 寻求正确的数组索引和
- 在此数组项中设置适当的位。
一个数组项中有BITSPERWORD （= 32）位，这意味着索引i必须分为两部分：
- 最右边的5位用作数组项中的索引
- 其余的位（最左边28位）用作数组的索引。
你得到：
- 通过丢弃最右边的五个 ， 最左边的28位 ，这正是
i>>SHIFT所做的，和 - 通过屏蔽除最右边的五位之外的任何东西，最右边的五位 ，这就是
i & MASK所做的。
我想你了解其余部分。
按位运算和Mask的前导段落是一个简明的解释，并包含一些进一步研究的指针。
将8位字节视为来自8个成员的宇宙中的一组元素。 当设置相应位时，成员处于集合中。 稍微设置一次不会修改集合成员资格 （一个位只能有2个状态）。 C中的按位运算符通过屏蔽和移位提供对位的访问。
代码试图通过数组存储N位，其中数组的每个元素包含BITSPERWORD （32）位。
因此，如果您尝试访问第i位，则需要计算存储它的数组元素的索引（ i/32 ），这就是i>>SHIFT所做的。
然后你需要在我们刚刚获得的数组元素中访问该位。
(i & MASK)给出数组元素（字）的位位置。 (1<<(i & MASK))使该位置的位置位。
现在您可以通过(1<在a[i>>SHIFT]设置/清除/测试该位。
您可能还认为i是32位数，位6~31是数组元素的索引存储它，位0~5表示字中的位位置。