解释用于设置,清除和测试单个位的算法

嘿,在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<<(i & MASK));
}

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

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

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

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

VonC总体上发布了关于位掩码的好答案.以下是您发布的代码更具体的一些信息.

给定一个表示位的整数,我们计算出该位的哪个成员保存该位.即:0到31位居住a[0],位32到63居住a[1],等等.所有这一切i>>SHIFT都是i / 32.这解决了a该位的哪个成员所在.使用优化编译器,这些可能是等效的.

显然,现在我们已经发现a该bitflag的哪个成员存在,我们需要确保在该整数中设置正确的位.这是做什么的1 << i.但是,我们需要确保不会尝试访问32位整数中的第33位,因此使用时可以限制移位操作1 << (i & 0x1F).这里的魔力0x1F是31,所以我们永远不会左移i三十多个位置所代表的位(否则它应该在下一个成员中移位a).

从这里(获得此线程的一般答案)

位掩码是一个值(可以存储在变量中),使您可以隔离整数类型中的特定位集.

通常,屏蔽将您感兴趣的位设置为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;

当你想在数组中设置一个位时,你必须这样做

寻求正确的数组索引和

在此数组项中设置适当的位.

BITSPERWORD一个数组项中有(= 32)位,这意味着索引i必须分为两部分:

最右边的5位用作数组项中的索引

其余的位(最左边28位)用作数组的索引.

你得到:

在通过丢弃最右边的最左边的五个28位,这正是i>>SHIFT做,和

在通过屏蔽掉什么,但最右边的五个位最右边的五个位,这是什么i & MASK呢.

我想你了解其余部分.