Thread: A BitVector class

  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
    Location
    Waterloo, Texas
    Posts
    5,708
    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:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed