5

嘿，在 Programming Pearls 书中，有一个源代码用于设置、清除和测试 int 数组中的一些给定索引，实际上是一个集合表示。

代码如下：

#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 定义的原因吗？它们在代码中的用途是什么？

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

4

5 回答 5

7

VonC 通常发布了一个关于位掩码的好答案。下面是一些更具体到您发布的代码的信息。

给定一个表示位的整数，我们计算出数组的哪个成员持有该位。即：位 0 到 31 位于 中a[0]，位 32 到 63 位于 中a[1]，依此类推。i>>SHIFT所做的只是i / 32。这可以确定位中的哪个成员a。使用优化编译器，这些可能是等价的。

显然，现在我们已经找到了该位标志的哪个成员a，我们需要确保我们在该整数中设置了正确的位。这就是这样1 << i做的。但是，我们需要确保不要尝试访问 32 位整数中的第 33 位，因此移位操作受到使用1 << (i & 0x1F). 这里的魔法0x1F是 31，所以我们永远不会左移i超过 31 个位置所代表的位（否则它应该在 的下一个成员中a）。

于 2008-11-06T07:22:27.443 回答
6

从这里（开始这个线程的一般答案）

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

通常，被屏蔽的位会将您感兴趣的位设置为 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;
于 2008-11-06T07:15:40.123 回答
5

当你想在数组中设置一个位时，你必须

  1. 寻找正确的数组索引和
  2. 在此数组项中设置适当的位。

一个数组项中有BITSPERWORD(=32) 位，这意味着必须将索引i分成两部分：

  • 最右边的 5 位用作数组项中的索引，并且
  • 其余位（最左边的 28 个）用作数组的索引。

你得到：

  • 最左边的 28 位通过丢弃最右边的五个，这正是i>>SHIFT所做的，并且
  • 通过屏蔽除最右边的五位以外的任何内容来屏蔽最右边的五位，这就是这样i & MASK做的。

我想你明白其余的。

于 2008-11-06T07:25:38.717 回答
0

位运算和Mask的前几段是一个简洁的解释，并包含一些进一步研究的指针。

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

于 2008-11-06T07:29:09.427 回答
0

该代码试图N通过数组存储位，其中数组的每个元素包含BITSPERWORD(32) 位。

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

然后你需要访问我们刚刚得到的数组元素中的那个位。

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

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

你也可能认为i是一个 32 位的数字，位 6~31 是存储它的数组元素的索引，位 0~5 代表字中的位位置。

于 2008-11-06T07:50:59.490 回答