bit vectors in c++ [closed]

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.

Circumscription

What do you want to know about bit vectors? In C++, you'd typically use std::bitset or std::vector<bool> for this – Arnaud

well, i dont even know what they are useful for, so anything will do) – Circumscription

also i would like to know what is bit vector's inner mechanics. sorry for bad english – Circumscription

i dont know a whole bunch of things. you have to learn in order to progress ) – Circumscription

true, but usually you choose to learn something because you have a reason; because you can see that it'd be relevant. There are billions of things that you, like everyone else, don't know. So why did you pick bit vectors specifically? My point is that you need some kind of context in order to learn anything useful. Otherwise, we have no way of determining what information we should give you. A bit vector is a vector of bits. I don't know what else to tell you, because you can't say what purpose the information serves for you – Arnaud

because i read about bit vectors in a book about data structures. but it provided no info on them. i felt curious. – Circumscription

by the way, just to be clear, I'm not saying you shouldn't learn about bit vectors, but rather that it's impossible for us to give you a useful answer if you don't ask something more specific – Arnaud

@jalf: I disagree. I think I gave the OP a useful answer. A trivial small implementation (with the bare essentials) along with a short explanation. – Calcium

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.

Calcium

What's the difference, if any, with bitset? – Teat

@Teat - ::std::bitset may not have existed at the time I wrote this. – Calcium

Answer 2

vector<​bool> is a specialization of the vector template. A normal bool variable requires at least one byte, but since a bool only has two states the ideal implementation of vector is such that each bool value only requires one bit. This means the iterator must be specially-defined, and cannot be a bool*.

from Thinking CPP Vol-2 from Bruce Eckel chapter 4: STL Containers & Iterators

The book can be downloaded for free at http://www.mindviewinc.com/Books/downloads.html and it contains more informations on bits and C++

Collodion