如何使用位运算实现位向量？

Question

我正在研究《编程珠玑》一书中的一个问题，他们推荐使用此函数来设置位向量中的位。但是我对它的作用有些困惑。

#define BITSPERWORD 32
#define MASK 0x1F
#define SHIFT 5
#define N 1000000

int a[1 + N/BITSPERWORD];

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

这里是我（可能错误的）对这段代码的解释：

如果i = 64，

1）首先，它将i向右移SHIFT（即5）位。这相当于将i除以2^5而不是乘以2^5，这点与我最初的想法不同。因此，如果i是64，则a的索引为2（64/2^5）。

2）a[2] |= (1 << (64 & MASK))， 64 & 1 = 1000000 & 01 = 1000001。 1会左移多少位？

- Henley

---

你确定 i 是 int 而不是 unsigned int 吗？这段代码是从哪里来的？ - Grijesh Chauhan

糟糕。好的，所以我更改为除以2 ^ 5。那其他的呢？ - Henley

(64 / 2^5) жҲ–иҖ…еҸӘжңү 2 (64 / 2^5) ... еҰӮжһң 1000 >> 1 == 0100пјҢйӮЈд№Ҳ x >> 5 е°ұзӯүдәҺ x / 2^5гҖӮ - Grijesh Chauhan

请注意，对于真正的代码，您可能希望使用std::bitset。它已经实现了大部分您想要的功能（可能还有更多）。 - Jerry Coffin

如果i == 64，则应为64＆MASK = 0。 - Jiminion

Answer 1

1. 这种方法似乎可以工作，尽管我觉得有更好的设置位的方式。它的原理是找到第 ith 位的索引值，实际上是将其除以32，因为每个单词有32位。
2. 由于在这里使用的是运算符|，该函数将位设置为1而不是切换位。
3. 0x1F实际上是31，当与i进行按位与操作时，您会获得余数（不确定为什么他们没有使用 %）。
4. 最后，移位将1移动到正确的位置，并将其与向量中的正确位置进行或运算。

如果您计划使用此代码

1. 您可以写得更加清晰，不使用宏定义，并使用更明显的方法来执行此操作，我怀疑速度方面不会有任何影响。
2. 此外，您应该只使用std::bitset。
3. 使用掩码获取余数的方法特别让我烦恼，因为我相信它不一定适用于每个数字，31之所以有效是因为它全是1。

- aaronman

---

+1 表示澄清 0X1F 是 31，我一直以为是 1。哇，这解决了很多问题。谢谢。 - Henley

@HenleyChiu 哈哈，没问题，说实话，有更清晰的方法来设置位，我不喜欢这段代码。 - aaronman