使用位实现集合
我正在阅读关于在以下位置表示为位的集合
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
}
要将一个项目插入到该集合中，我们需要将位数组中的相应位更改为1。 位阵列的第i位是字i上限（i / w）的位i我mod。 因此，如上面的程序所示，插入功能是通过按位或操作将第i位更改为1来实现的。 尽管它比SetAsArray类的相应操作稍微复杂一些，但此操作的运行时间仍为O（1）。 由于w = wordBits是2的幂，所以可以用这样的移位和掩码来替换除法和模运算：/和％：
矢量[item >> shift] | = 1 <<（item＆mask）;
根据编译器和机器体系结构的不同，这样做可以通过一个常数来提高插入操作的性能
问题
我在构造函数中的问题为什么作者将wordBits添加到“n”并减去1，而不是直接用作n / wordbits？
第二个问题是作者的意思是声明“ince w = wordBits是2的幂，可以用这样的换挡和掩码代替除法和模运算，/和％：
矢量[item >> shift] | = 1 <<（item＆mask）;
在上述情况下，请示例举例说明什么是移位和掩码的值。
我将它重新标记为C ++，因为它显然不是C.
n等于小于wordBits东西来调用它会发生什么。 通用公式正是使用的公式，即b = (a + Q - 1) / Q确保b * Q至少为a 。