implemenation of sets using bits

I am reading about sets representing as bits at following location

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

Questions

My question in constructor why author adding wordBits to "n" and subtracting 1, instead we can use directly as n/wordbits?

Second question whay does author mean by statement "ince 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);

Reequest to give an example in case of above scenario what is value of shift and mask.

Why author mentioned depending on architecture and compiler there is improve in performance?

---

I re-tagged this as C++, since it's clearly not C.

To round up. Consider what happens if you call it with n equal to something smaller than wordBits for instance. The generic formula is exactly the one being used, ie b = (a + Q - 1) / Q makes sure b * Q is at least a .

Basic binary arithmmetic, division by two is equivalent with shifting to the right and so on.

On some machines, bitwise operations like shifts and masks are faster than divisions and modulos.

链接地址: http://www.djcxy.com/p/72676.html

上一篇: 按位运算符可能具有未定义的行为？

下一篇: 使用位实现集合