c++ - 使用位实现集合

Question

我正在阅读有关在以下位置表示为位的集合

http://www.brpreiss.com/books/opus4/html/page395.html

class SetAsBitVector : public Set

{

   typedef unsigned int Word;

   enum { wordBits = bitsizeof (Word) };


   Array<Word> vector;


public:

    SetAsBitVector (unsigned int);

    // ...

};

SetAsBitVector::SetAsBitVector (unsigned int n) :
    Set (n),

                                                     vector ((n + wordBits - 1U) / wordBits)
{
  // Question here?
   for (unsigned int i = 0; i < vector.Length (); ++i)

    vector [i] = 0;

}

void SetAsBitVector::Insert (Object& object)
{

   unsigned int const item = dynamic_cast<Element&> (object);

   vector [item / wordBits] |= 1 << item % wordBits;
  // Question here
}

To insert an item into the set, we need to change the appropriate bit in the array of bits to one. The ith bit of the bit array is bit i mod w of word ceiling(i/w). Thus, the Insert function is implemented using a bitwise or operation to change the ith bit to one as shown in above Program . Even though it is slightly more complicated than the corresponding operation for the SetAsArray class, the running time for this operation is still O(1). Since w = wordBits is a power of two, it is possible to replace the division and modulo operations, / and %, with shifts and masks like this:

vector [item >> shift] |= 1 << (item & mask);

Depending on the compiler and machine architecture, doing so may improve the performance of the Insert operation by a constant factor

问题

1. 我在构造函数中的问题为什么作者将 wordBits 添加到“n”并减去 1，而不是我们可以直接用作 n/wordbits？

2. 第二个问题作者的意思是“因为 w = wordBits 是 2 的幂，所以可以用这样的移位和掩码替换除法和模运算，/和 %:

vector [item >> shift] |= 1 << (item & mask);

要求在上述情况下给出一个例子，shift 和 mask 的值是多少。

1. 为什么作者提到根据体系结构和编译器可以提高性能？

Answer 1

我将其重新标记为 C++，因为它显然不是 C。

1. 四舍五入。例如，考虑一下如果您使用小于 wordBits 的 n 调用它会发生什么。通用公式正是使用的公式，即 b = (a + Q - 1)/Q 确保 b * Q 至少是 a.
2. 基本的二进制算术，除以2等价于右移等。
3. 在某些机器上，移位和掩码等按位运算比除法和取模运算更快。