一个算法的说明设置,清除和测试一个位
嘿,在编程珍珠书中,有一个源代码用于设置,清除和测试一个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和掩模限定的原因是什么?他们在代码中的目的是什么?
我已经阅读过以前的相关question。
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
的下一位成员中去掉)。
从Here(一般的回答让这个线程开始)
位掩码是一个值(其可以存储在一个变量),使您可以整数类型中分离出一组特定的位。
正常情况下,被屏蔽的位将您感兴趣的位设置为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-09 04:07:01
当你想设置一个位阵列内,你必须
- 寻求正确的数组索引和
- 设置相应的位这个数组的项目里面。
有BITSPERWORD
(= 32)在一个阵列中的项目,这意味着该索引i
必须被分成两个部分位:
- 最右边的5位作为在阵列项的索引和
- 其余的位(最左边的28)用作数组的索引。
你得到:
- 的最左边的28位通过丢弃最右边的5,这正是
i>>SHIFT
确实,和 - 的最右边的五个位元掩盖了什么,但最右边的五位,这是什么
i & MASK
呢。
我想你了解其余的。
Bitwise operation和Mask的引导段落是一个简明的解释,并包含一些指针供进一步研究。
将8位字节看作是来自8个成员的Universe中的一组元素。一个成员是IN当相应位置位时置位。多设置一次不会修改set membership(一个位只能有2个状态)。 bitwise operators in C提供对掩码和移位的位访问。
代码试图按数组存储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位表示该单词中的位位置。
+1,比我的一般答案更准确。 – VonC 2008-11-06 07:25:42
谢谢,那正是我所需要的。 – 2008-11-06 07:31:52