3

我正在研究编程珍珠一书中的一个问题，他们推荐这个函数在位向量中设置一个位。我对它的作用有点困惑。

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

这是我对这段代码的（可能是错误的）解释。如果我 = 64，

1）首先，它将i它向右移动 SHIFT（即 5）位。这相当于除以 （而不是像我最初想到的那样相乘i）2^5。所以如果i是64，则 a 的索引是2 (64 / 2^5)

2) a[2] |= (1 << (64 & MASK))
64 & 1 = 1000000 & 01 = 1000001。
所以 1 左移了多少位？？？？

4

1 回答 1

3
  1. 看起来这种方法是如何工作的，尽管我觉得有更好的方法来设置一点。是找到ith它基本上除以 32 的位的索引，因为这是每个字的位数。
  2. 由于此处使用的运算符是|函数将位设置为不切换位
  3. 0x1F 实际上是 31 并且当与 i 与你得到余数时（不知道他们为什么不使用%）
  4. 最后，移位将 1 带到正确的位置，或者将其与向量中的正确插槽一起使用。

如果您打算使用此代码

  1. 您可以在没有定义并使用更明显的方法的情况下将其写得很清楚，我怀疑它会在速度上有所不同。
  2. 你也应该只使用std::bitset
  3. 使用掩码来获取余数让我特别恼火，因为我很确定它不一定对每个数字都有效，31 恰好有效，因为它都是 1
于 2013-07-20T17:29:42.997 回答