一个算法的说明设置，清除和测试一个位

嘿，在编程珍珠书中，有一个源代码用于设置，清除和测试一个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。

来源

2008-11-06 jaircazarin-old-account

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-06 07:22:27

+1，比我的一般答案更准确。 – VonC 2008-11-06 07:25:42

谢谢，那正是我所需要的。 – 2008-11-06 07:31:52

从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-06 07:15:40 VonC

很好的解释！再有那个追踪者...... – 2008-11-09 04:07:01

当你想设置一个位阵列内，你必须

寻求正确的数组索引和
设置相应的位这个数组的项目里面。

有BITSPERWORD（= 32）在一个阵列中的项目，这意味着该索引i必须被分成两个部分位：

最右边的5位作为在阵列项的索引和
其余的位（最左边的28）用作数组的索引。

你得到：

的最左边的28位通过丢弃最右边的5，这正是i>>SHIFT确实，和
的最右边的五个位元掩盖了什么，但最右边的五位，这是什么i & MASK呢。

我想你了解其余的。

来源

2008-11-06 07:25:38 zoul

Bitwise operation和Mask的引导段落是一个简明的解释，并包含一些指针供进一步研究。

将8位字节看作是来自8个成员的Universe中的一组元素。一个成员是IN当相应位置位时置位。多设置一次不会修改set membership（一个位只能有2个状态）。 bitwise operators in C提供对掩码和移位的位访问。

来源

2008-11-06 07:29:09 gimel

代码试图按数组存储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位表示该单词中的位位置。

来源

2008-11-06 07:50:59 tingyu

一个算法的说明设置，清除和测试一个位

回答

相关问题