A BitVector class

This is a discussion on A BitVector class within the C++ Programming forums, part of the General Programming Boards category; Hello there all, I am enrolled in a Data Structures class and we are studying the structure called bitvector. It's ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    A BitVector class

    Hello there all,
    I am enrolled in a Data Structures class and we are studying the structure called bitvector. It's a really interesting course... one that actually makes use of C++ other than doing some simple "Hello World" type programs assigned to us in the introductory course of C++.
    Anyway, my question to you all is this. For those of you that do know, a bitvector can be manipulated in the bit level. I understand how to access at the bit level. You access the kth bit by:
    1) Performing integer division by 8
    2) Performing a "mask" at the kth bit
    This is done in code like so:
    Code:
      void BitVector::Set(unsigned int index)
        // make bit = 1
      {
        // Access the bit k, by integer dividing index by 8
        // and shifting index % 8
        unsigned byte = Array[index/8];
        unsigned bit = Test(index);
      }
    where Test is:
    Code:
      int BitVector::Test(unsigned int index) const
        // tests whether a bit is turned 'on' or 'off'
      {
        return (Array[ByteNumber(index)] & Mask(index)) != 0;
      }
    My question is now that you have accessed it, how do you manipulate at the bit level?? An explanation over code is much more appreciated. Thank you for your time.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Posts
    5,439
    First consider how an integer is set, cleared, and tested:

    Code:
    bool test(unsigned data, char bit)
    {
     return data & (1 << bit);
    }
    
    void set(unsigned * data, char bit)
    {
     *data |= (1 << bit);
    }
    
    void clear(unsigned * data, char bit)
    {
     *data &= ~(1 << bit);
    }
    So for an integer, the valid indexes would be 0-31. A bit vector just lets you do it 'more intuitively' plus allows you to have say a 236 bit piece of data (I'm assuming here - never used a 'bitvector' myself). Either way, the bitvector class simply maps the index you specify into the internal bit of interest. Manipulating the bit would be done through a member function of course.
    Code:
    int main(void){srand(time(0));for(double l=rand(),l0=0,l00=0;;l0+=0.1){for(double l000=0;l000
    <1;l000+=.001,l+=((double)rand()/RAND_MAX)/0x64,l00+=((sin(l*0x8*atan(l0)*l000-(l0*0x8*atan
    (l)))*0.5)+0.5)){l00-=floor(l00);for(size_t l0000=0,l00000=(size_t)(0x50*(l00));l0000<l00000;++l0000
    )putchar(0x20);putchar(0x61+(int)((double)rand()/RAND_MAX*0x1a));putchar('\n');}}return 0;}

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21