bit vectors in c++

Question

Recently I heard about bit vectors, but i cant really find any useful info or tutorials on this topic. Can you please suggest a book or a quick tutorial on how to implement your own bit vector classes? Thank you.

---/// i cant post answers to my own questions, so i decided to edit this post. here is what i have just found: "Data Structure for Game Programmers - Ron Penton and Andre Lamothe". Chapter 4, Bitvectors. This book has thorough explanation of bit vectors, and how to make a bit vector class yourself. have fun.

Answer 1

Here is a very simple statically sized bit vector implementation. It requires C++11 to function since it relies on the <cstdint> header, but this header is fairly commonly found since it's based on a C99 feature. In a pinch you can use the C <stdint.h> header and simply use types in the global namespace instead.

Note: This was typed on-the-fly and isn't tested at all. I didn't even verify it would compile. So, there may be errors.

#include <cstdint>  // ::std::uint64_t type
#include <cstddef> // ::std::size_t type
#include <algorithm>

class my_bitvector_base {
 protected:
   class bitref { // Prevent this class from being used anywhere else.
    public:
      bitref(::std::uint64_t &an_int, ::std::uint64_t mask)
           : an_int_(an_int), mask_(mask)
      {
      }

      const bitref &operator =(bool val) {
         if (val) {
            an_int_ |= mask_;
         } else {
            an_int_ &= ~mask_;
         }
         return *this;
      }
      const bitref &operator =(const bitref &br) {
         return this->operator =(bool(br));
      }
      operator bool() const {
         return ((an_int_ & mask_) != 0) ? true : false;
      }

    private:
      ::std::uint64_t &an_int_;
      ::std::uint64_t mask_;
   };
};

template < ::std::size_t Size >
class my_bitvector : public my_bitvector_base {
 private:
   static constexpr ::std::size_t numints = ((Size + 63) / 64);
 public:
   my_bitvector() { ::std::fill(array, array + numints, 0); }

   bool operator [](::std::size_t bitnum) const {
      const ::std::size_t bytenum = bit / 64;
      bitnum = bitnum % 64;
      return ((ints_[bytenum] & (::std::uint64_t(1) << bitnum)) != 0) ? true : false;
   }
   bitref operator[](::std::size_t bitnum) {
      const ::std::size_t bytenum = bit / 64;
      bitnum = bitnum % 64;
      ::std::uint64_t mask = ::std::uint64_t(1) << bitnum;
      return bitref(ints_[bytenum], mask);
   }

 private:
   ::std::uint64_t ints_[numints];
};

// Example uses
void test()
{
    my_bitvector<70> bits; // A 70 bit long bit vector initialized to all false
    bits[1] = true; // Set bit 1 to true
    bool abit = bits[1]; // abit should be true.
    abit = bits[69]; // abit should be false.
}

The whole my_bitvector_base thing is to create a sort of private type. You can mention it in the interface or implementation for derived classes because it's protected, but you can't mention it other contexts. This prevents people from storing a copy of a bitref. This is important because a bitref only really exists to allow assignment to the result of operator [] because the C++ standards committee, in all their wisdom, has not implemented operator []= or something similar for assigning to an array element.

As you can see, a bit vector is basically an array of bits. Fancier bit vectors will simulate an 'infinite' array of bits all initialized to true or false. They do this by tracking the very last bit that has been set and all bits before it. And if you ask for a bit after that, they just return the initialized value.

A good bit vector will also implement operator & and other such niceties so they behave sort of like a very large unsigned integer with reference to bit manipulation operations.