在下面的编程珠玑示例程序中使用了位掩码，请问它是如何使用的？

Question

我今天开始阅读《编程珠玑》这本书，在做练习时遇到了这个问题：“你会如何实现自己的位向量？” 当我看到解决方案时，它是这样的：

#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)); 

我感到困惑的是这个陈述。

 1 << (i & MASK)

能否有人解释一下这里正在发生什么？

- test123

Answer 1

请注意，MASK 被设置为具有最低的 SHIFT 位被设置，其中 SHIFT 精确地是以2为底数的对数 BITSPERWORD。

因此，(i & MASK) 将选择 i 的最低5位，这与取模32后的余数相同（只需考虑如何在十进制数中取最低两位数字，例如得到100的余数）。这给出了我们感兴趣的一个字内的位数。

现在，1 << (i & MASK)) （顺便说一下，这是一个表达式而不是语句）创建一个值，其中恰好设置了我们感兴趣的位。将此值与内存单元合并使用 |= 将设置位向量的所需位。

- hmakholm left over Monica

---

谢谢您的回复，亨宁。如果我将(i & MASK)替换为(i % 32)，这样做是否有效？如果这样做是有效的但不够优雅，那么能否请您解释一下为什么i & MASK比i % 32更受欢迎？非常感谢。 - test123

是的--只要你确定“i”不是负数，“i & MASK”和“i % 32”是同样的东西。位与运算通常比除法带余要更高效，因此已成为传统选择。或者至少在编译器还很愚蠢的时候是这样。今天，即使是中度优化的编译器，在这种情况下也可以预期将“i％32”在内部重写为“i＆31”（无论它能否证明“i”不是负数，在这种情况下重新编写总是安全的，或者它可以推理出负结果会在移位中触发未定义的行为）。 - hmakholm left over Monica

Answer 2

0x20等于32，所以i & 0x1F对32取模，确保你不会移位32位。这是一种保护措施，因为移位超过类型大小的任何值都是未定义的行为。

- Kerrek SB