"infinite" capacity int

I spent the better part of the last 2 days implementing my own int class, Int. Its slow, poorly written and I would'nt ask my worst enimy to use it in production code.

BUT! It handles "infinitely" large numbers (the bits are stored in a vector<bool>) and it supports all the important operators defined for int. It can also be converted to a string for display.

At least now I have proof that I can do it, and I learned a lot, so I guess it was not totally useless.

EDIT: I'm putting the code up here

#include <vector>
#include <string>
#include <cstring>

using namespace std;



#define MAX(a, b) ((a)>(b) ? (a) : (b))
#define MIN(a, b) ((a)<(b) ? (a) : (b))



/******************************************************\
* Purpose: An int class without overflow but unlimited capacity.             *
\******************************************************/
class Int{
  public:
    Int():Bits(0){};

    Int(const Int& Num):Bits(Num.Bits){};


/* Not tested...

    // Simply assumes numeric string.
    Int(string Num){
      Int PosValue = 1;
      for(int i=Num.size(); i>=0; i--){
        *this += ((Int)((int)(Num[i] - '0'))) * PosValue;
        PosValue = PosValue * Int(10);
      }
    };

*/

    Int(int Num):Bits(sizeof(int)*8){
      // Copy each bit to the internal representation.
      for(int i=0; i<sizeof(int)*8; i++)
        Bits[i] = ((*(unsigned int*)&Num)>>i) & 1;
    };
    
// This is the default implementation anyway.
//    operator =(const Int& Num){
//      Bits = Num.Bits;
//    };

    // Only works for (GetBitCount <= sizeof(int)*8).
    int ToInt() const{
      // We need the sign-bit in the right place.
      Int Temp = *this;
      Temp.SetBitCount(sizeof(int)*8);
      
      // Copy bit-wise to a regular int.
      int Num = 0;
      for(int i=0; i<Temp.Bits.size() && i<sizeof(int)*8; i++)
        (*(unsigned int*)&Num) |= Temp.Bits[i]<<i;
      return Num;
    };

    string ToBits() const{
      // Just copy each bit to a string of 1's and 0's.
      vector<char> Num(Bits.size()+1);
      for(int i=0; i<Bits.size(); i++)
        Num[Bits.size()-1-i] = Bits[i] ? '1' : '0';
      Num[Bits.size()] = 0;
      return string(&Num[0]);
    };

    string ToString() const{
      // Set the value of the position of the first char. (10^NumChars)
      Int CharValue(1);
      while(CharValue <= *this)
        CharValue = CharValue * Int(10);
      CharValue = CharValue / Int(10);

      // Step through each charakter in the string.
      vector<char> Num;
      Int Reminder(*this);
      while(1){
        // Check how many times CharValue can "fit" in Reminder, then subtract.
        Int Char = Reminder / CharValue;
        Reminder -= Char * CharValue;

        Num.push_back(Char.ToInt() + '0');

        // Take the next char.
        CharValue = CharValue / Int(10);
        if(CharValue == Int(0)) break;
      }

      // Null-terminate.
      Num.push_back(0);

      return string(&Num[0]);
    };


    Int operator+(const Int& Num)const{
      // Some temps.
      Int Out(0);
      Int A(Num);
      Int B(*this);

      // Make booth terms and the result equally long.
      Out.SetBitCount(MAX(A.GetBitCount(), B.GetBitCount())+1); // No overflow!
      A.SetBitCount(Out.GetBitCount());
      B.SetBitCount(Out.GetBitCount());

      // Bitwise addition with a carry-bit.
      bool Carry = false;
      for(int i=0; i<Out.GetBitCount(); i++){
        Out.Bits[i] = (A.Bits[i] ^ B.Bits[i] ^ Carry) & 1;  
        Carry = (A.Bits[i] && B.Bits[i]) || (Carry && (A.Bits[i] || B.Bits[i]));
      }

      // Optimize. (We don't want the bitcount to grow out of hand.)
      Out.MinimizeBitCount();
      return Out;
    };

    void operator+=(const Int& Num){
      *this = *this + Num;
    };

    Int operator-()const{
      Int Num = *this;

      // Invert each bit.
      for(int i=0; i<Num.Bits.size(); i++)
        Num.Bits[i] = !Num.Bits[i];
        
      // Add one.
      Num += Int(1);

      return Num;
    };

    Int operator-(const Int& Num)const{
      return *this + -Num;
    };

    void operator-=(const Int& Num){
      *this = *this + -Num;
    };

    bool operator<(const Int& Num)const{
      Int Diff = *this - Num;
      // Check if the difference is negative.
      return Diff.Bits.size() && Diff.Bits[Diff.Bits.size()-1];
    };

    bool operator>(const Int& Num)const{return Num < *this;};

    bool operator<=(const Int& Num)const{return !(*this > Num);};

    bool operator>=(const Int& Num)const{return !(*this < Num);};

    bool operator==(const Int& Num)const{
      return (!(*this<Num)) && (!(*this>Num)) ;
    };

    bool operator!=(const Int& Num)const{return !(*this==Num);};

    Int operator>>(const unsigned int Num)const{
      Int Out;
      Out.SetBitCount(MAX((int)GetBitCount() - (int)Num, 0)); 
      
      // Just copy the topmost bits.
      for(int i=0; i<Out.GetBitCount(); i++)
        Out.Bits[i] = Bits[i+Num];

      return Out;
    };

    Int operator<<(const unsigned int Num)const{
      Int Out;

      // Make shure the upshift will add bits according to the sign.
      if(*this<Int(0))
        Out = Int(-1);

      // Grow.
      Out.SetBitCount(GetBitCount() + Num);
      
      // Fill.
      for(int i=Num; i<Out.GetBitCount(); i++)
        Out.Bits[i] = Bits[i-Num];

      return Out;
    };

    Int operator*(const Int& Num)const{
      // Some temps.
      Int Out;
      Int A(Num);
      Int B(*this);
      
      // Make booth terms positive, but save the sign.
      bool Sign = false;
      if(A < Int(0)){
        A = -A;
        Sign = !Sign;
      }
      if(B < Int(0)){
        B = -B;
        Sign = !Sign;
      }
        
      // Multiply each pair (A[i]&(1<<i), B[j]&(1<<j)) and sum the results.
      for(int i=0; i<A.GetBitCount(); i++){
        Int Temp;
        Temp.SetBitCount(i+B.GetBitCount());
        for(int j=0; j<B.GetBitCount(); j++){
          Temp.Bits[i+j] = A.Bits[i] && B.Bits[j];  
        }

        Out += Temp;
      }
      
      // Apply sign.
      if(Sign) Out = -Out;
      
      return Out;
    };

    Int operator/(const Int& Num)const{
      // Some temps.
      Int Out;
      Int A(*this);
      Int B(Num);

      // Div. by 0. "Undefined behavour." (It might send pr0n spam to your mom.)
      if(Num == Int(0)) return Out;

      // Make shure A is bigger/equal to B. (Otherwise Out is zero anyway.)
      if(A<B) return Out;

      // Make booth terms positive, but save the sign.
      bool Sign = false;
      if(A < Int(0)){
        A = -A;
        Sign = !Sign;
      }
      if(B < Int(0)){
        B = -B;
        Sign = !Sign;
      }
        
      A.MinimizeBitCount();
      B.MinimizeBitCount();
      Out.SetBitCount(A.GetBitCount()-B.GetBitCount()+2);
      // This loops just checks how many times you can subtract B from A, but
      //  it will start with B*(2^n), decreasing n each loop. 
      for(int i=A.GetBitCount()-B.GetBitCount(); i>=0; i--){
        Int a = A - (B<<i);
        
        if(a >= Int(0)){
          Out.Bits[i] = true;
          A = a;
        }
      }
      
      // Apply sign.
      if(Sign) Out = -Out;
      
      return Out;
    };

    unsigned int GetBitCount() const{
      return Bits.size();
    };

    bool SetBitCount(unsigned int NewCount){
      if(NewCount > GetBitCount()){
        int OldCount = Bits.size();

        // Add the new bits.
        Bits.resize(NewCount);

        // Set the new bits to match positive/negative content.
        bool Sign = OldCount ? Bits[OldCount-1] : false;
        for(int i=OldCount; i<NewCount; i++)
          Bits[i] = Sign;
          
        return true;
      }
      return false;
    };

    void MinimizeBitCount(){
      int SignBit = Bits.size()-1;
      bool Sign = Bits[SignBit];
      
      // Step backwards until the first "used" bit is found.
      while(SignBit && Bits[SignBit-1] == Sign) SignBit--;

      if(Sign && SignBit==0) Bits.resize(1); // If it is negative, we must keep the signbit.
      else Bits.resize(SignBit+1);
    };

  private:
    vector<bool> Bits;
};

What good is this topic if you don't post the code?

*directs geon to the code gem submission page*

I'm guessing if you're using vector<bool> that each bool is treated like a single bit. Would it not be better to use a vector<unsigned char>, and treat each one as a byte (which it almost always is). That way you won't waste bits, as I very much doubt a bool is 1 bit in size .

You could even do something clever with a vector<int> and sizeof() so that it works on all platforms, and reduces the number of elements in the vector.

Correct me if I'm wrong, but I thought vector<bool> was meant as an example of template specialization, and it uses 1 bit per bool value. Of course, this breaks a lot of things that people take for granted with regular vectors. For example, assuming that dereferencing the first index of the vector points to a contiguous array in memory of the value type.

monjardin: you are correct . std::vector<bool> is specialized to be stored as actual bits. When referencing a single element in the vector, you won't get a bool& but instead a type that typically holds a reference to the int where that bit is stored, and a bit index in that int. Retrieving or assigning a bool value to this type will read/write the actual bit in the array.

I would prefer std::bitset for such things, but if it works...

AFAIK the standard committee will likely remove that std::vector<bool> template specialisation because it has too many drawbacks.

IIRC bitset has a fixed compile time size (by a template argument). So that's not very usefull if you want to expand the "wordsize" of your int to hold arbitrary large values.

Though it might be interesting to have a std::vector<int> anyway. That way you can process 32 bits (or whatever) at once. of course you'll probably need a bit of assembly to get the carries right =)

Bramz

Originally Posted by bramz

of course you'll probably need a bit of assembly to get the carries right =)

Nah

unsigned oldValue = value;
value += addition;
if (value < oldValue)
     carry = 1;

Of course, an 'add' followed by a series of 'adc' instructions is much more performant

Originally Posted by bramz

Though it might be interesting to have a std::vector<int> anyway. That way you can process 32 bits (or whatever) at once.
Bramz

I thought about that too, and it will possibly be the next step. However, the greatest bottleneck is my division algorithm. I simply have no idea about how to implement division effectively with "chunks" of bits (like an int).

If anyone has ideas or links on that, feel free to share them. I'm all ears...

Added as a Code Gem.

Could some moderator join the threads, please?

We can join the threads as soon as the new code gem becomes visible (it updates at 10AM EST, so soon).

I stand corrected, I didn't know that about vectors. Yet another thing the SGI documentation is lacking I guess.

http://www.dinkumware.com/refxcpp.html (click that image with footprints)
http://www.kuzbass.ru/docs/isocpp/

I wrote some stupid code to handle "infinitely" large ints. Just felt I had to do it...

Anyway, here it is. I make no claims about it's usefullness, but it works and is pretty readable, so someone might find it "educational".

#include <vector>
#include <string>
#include <cstring>

using namespace std;



#define MAX(a, b) ((a)>(b) ? (a) : (b))
#define MIN(a, b) ((a)<(b) ? (a) : (b))



/******************************************************\
* Purpose: An int class without overflow but unlimited capacity.             *
\******************************************************/
class Int{
  public:
    Int():Bits(0){};

    Int(const Int& Num):Bits(Num.Bits){};


/* Not tested...

    // Simply assumes numeric string.
    Int(string Num){
      Int PosValue = 1;
      for(int i=Num.size(); i>=0; i--){
        *this += ((Int)((int)(Num[i] - '0'))) * PosValue;
        PosValue = PosValue * Int(10);
      }
    };

*/

    Int(int Num):Bits(sizeof(int)*8){
      // Copy each bit to the internal representation.
      for(int i=0; i<sizeof(int)*8; i++)
        Bits[i] = ((*(unsigned int*)&Num)>>i) & 1;
    };
    
// This is the default implementation anyway.
//    operator =(const Int& Num){
//      Bits = Num.Bits;
//    };

    // Only works for (GetBitCount <= sizeof(int)*8).
    int ToInt() const{
      // We need the sign-bit in the right place.
      Int Temp = *this;
      Temp.SetBitCount(sizeof(int)*8);
      
      // Copy bit-wise to a regular int.
      int Num = 0;
      for(int i=0; i<Temp.Bits.size() && i<sizeof(int)*8; i++)
        (*(unsigned int*)&Num) |= Temp.Bits[i]<<i;
      return Num;
    };

    string ToBits() const{
      // Just copy each bit to a string of 1's and 0's.
      vector<char> Num(Bits.size()+1);
      for(int i=0; i<Bits.size(); i++)
        Num[Bits.size()-1-i] = Bits[i] ? '1' : '0';
      Num[Bits.size()] = 0;
      return string(&Num[0]);
    };

    string ToString() const{
      // Set the value of the position of the first char. (10^NumChars)
      Int CharValue(1);
      while(CharValue <= *this)
        CharValue = CharValue * Int(10);
      CharValue = CharValue / Int(10);

      // Step through each charakter in the string.
      vector<char> Num;
      Int Reminder(*this);
      while(1){
        // Check how many times CharValue can "fit" in Reminder, then subtract.
        Int Char = Reminder / CharValue;
        Reminder -= Char * CharValue;

        Num.push_back(Char.ToInt() + '0');

        // Take the next char.
        CharValue = CharValue / Int(10);
        if(CharValue == Int(0)) break;
      }

      // Null-terminate.
      Num.push_back(0);

      return string(&Num[0]);
    };


    Int operator+(const Int& Num)const{
      // Some temps.
      Int Out(0);
      Int A(Num);
      Int B(*this);

      // Make booth terms and the result equally long.
      Out.SetBitCount(MAX(A.GetBitCount(), B.GetBitCount())+1); // No overflow!
      A.SetBitCount(Out.GetBitCount());
      B.SetBitCount(Out.GetBitCount());

      // Bitwise addition with a carry-bit.
      bool Carry = false;
      for(int i=0; i<Out.GetBitCount(); i++){
        Out.Bits[i] = (A.Bits[i] ^ B.Bits[i] ^ Carry) & 1;  
        Carry = (A.Bits[i] && B.Bits[i]) || (Carry && (A.Bits[i] || B.Bits[i]));
      }

      // Optimize. (We don't want the bitcount to grow out of hand.)
      Out.MinimizeBitCount();
      return Out;
    };

    void operator+=(const Int& Num){
      *this = *this + Num;
    };

    Int operator-()const{
      Int Num = *this;

      // Invert each bit.
      for(int i=0; i<Num.Bits.size(); i++)
        Num.Bits[i] = !Num.Bits[i];
        
      // Add one.
      Num += Int(1);

      return Num;
    };

    Int operator-(const Int& Num)const{
      return *this + -Num;
    };

    void operator-=(const Int& Num){
      *this = *this + -Num;
    };

    bool operator<(const Int& Num)const{
      Int Diff = *this - Num;
      // Check if the difference is negative.
      return Diff.Bits.size() && Diff.Bits[Diff.Bits.size()-1];
    };

    bool operator>(const Int& Num)const{return Num < *this;};

    bool operator<=(const Int& Num)const{return !(*this > Num);};

    bool operator>=(const Int& Num)const{return !(*this < Num);};

    bool operator==(const Int& Num)const{
      return (!(*this<Num)) && (!(*this>Num)) ;
    };

    bool operator!=(const Int& Num)const{return !(*this==Num);};

    Int operator>>(const unsigned int Num)const{
      Int Out;
      Out.SetBitCount(MAX((int)GetBitCount() - (int)Num, 0)); 
      
      // Just copy the topmost bits.
      for(int i=0; i<Out.GetBitCount(); i++)
        Out.Bits[i] = Bits[i+Num];

      return Out;
    };

    Int operator<<(const unsigned int Num)const{
      Int Out;

      // Make shure the upshift will add bits according to the sign.
      if(*this<Int(0))
        Out = Int(-1);

      // Grow.
      Out.SetBitCount(GetBitCount() + Num);
      
      // Fill.
      for(int i=Num; i<Out.GetBitCount(); i++)
        Out.Bits[i] = Bits[i-Num];

      return Out;
    };

    Int operator*(const Int& Num)const{
      // Some temps.
      Int Out;
      Int A(Num);
      Int B(*this);
      
      // Make booth terms positive, but save the sign.
      bool Sign = false;
      if(A < Int(0)){
        A = -A;
        Sign = !Sign;
      }
      if(B < Int(0)){
        B = -B;
        Sign = !Sign;
      }
        
      // Multiply each pair (A[i]&(1<<i), B[j]&(1<<j)) and sum the results.
      for(int i=0; i<A.GetBitCount(); i++){
        Int Temp;
        Temp.SetBitCount(i+B.GetBitCount());
        for(int j=0; j<B.GetBitCount(); j++){
          Temp.Bits[i+j] = A.Bits[i] && B.Bits[j];  
        }

        Out += Temp;
      }
      
      // Apply sign.
      if(Sign) Out = -Out;
      
      return Out;
    };

    Int operator/(const Int& Num)const{
      // Some temps.
      Int Out;
      Int A(*this);
      Int B(Num);

      // Div. by 0. "Undefined behavour." (It might send pr0n spam to your mom.)
      if(Num == Int(0)) return Out;

      // Make shure A is bigger/equal to B. (Otherwise Out is zero anyway.)
      if(A<B) return Out;

      // Make booth terms positive, but save the sign.
      bool Sign = false;
      if(A < Int(0)){
        A = -A;
        Sign = !Sign;
      }
      if(B < Int(0)){
        B = -B;
        Sign = !Sign;
      }
        
      A.MinimizeBitCount();
      B.MinimizeBitCount();
      Out.SetBitCount(A.GetBitCount()-B.GetBitCount()+2);
      // This loops just checks how many times you can subtract B from A, but
      //  it will start with B*(2^n), decreasing n each loop. 
      for(int i=A.GetBitCount()-B.GetBitCount(); i>=0; i--){
        Int a = A - (B<<i);
        
        if(a >= Int(0)){
          Out.Bits[i] = true;
          A = a;
        }
      }
      
      // Apply sign.
      if(Sign) Out = -Out;
      
      return Out;
    };

    unsigned int GetBitCount() const{
      return Bits.size();
    };

    bool SetBitCount(unsigned int NewCount){
      if(NewCount > GetBitCount()){
        int OldCount = Bits.size();

        // Add the new bits.
        Bits.resize(NewCount);

        // Set the new bits to match positive/negative content.
        bool Sign = OldCount ? Bits[OldCount-1] : false;
        for(int i=OldCount; i<NewCount; i++)
          Bits[i] = Sign;
          
        return true;
      }
      return false;
    };

    void MinimizeBitCount(){
      int SignBit = Bits.size()-1;
      bool Sign = Bits[SignBit];
      
      // Step backwards until the first "used" bit is found.
      while(SignBit && Bits[SignBit-1] == Sign) SignBit--;

      if(Sign && SignBit==0) Bits.resize(1); // If it is negative, we must keep the signbit.
      else Bits.resize(SignBit+1);
    };

  private:
    vector<bool> Bits;
};

Originally Posted by Axel

I would prefer std::bitset for such things, but if it works...

AFAIK the standard committee will likely remove that std::vector<bool> template specialisation because it has too many drawbacks.

That was a really crazy thing for them to include it in the std in the first place

FYI, you can use the std::max and std::min template functions from the STL instead of defining your own macros.

Great! Now C++ can do this without Python's help. I wonder, though, if there are routines for this in the Python24.dll .

Could you edit the code and remove the MIN and MAX macros as they promote really bad coding habits - almost as bad as defining "min" and "max" as what windows headers do. The std::min and std::max functions should be enough as Monjardin noted. If you really want to do the min and max operations yourself, then why not making them as templated functions instead of macros. I'd also use explicit std:: prefix when needed and not do "using namespace std;"

edit:

Ok.. now when I started this nitpicking. this code also gives some warnings due to conversion between types "for(int i=0; i<Bits.size(); i++)" could be replaced by "for (size_t i=0; i<Bits.size(); ++i).

However, thanks for posting this and keeping the code snapshot alive

Your code looks interesting =) But I have a few suggestions that might improve its quality:

- as mojardin and juhnu already said: use std::min and std::max

- as juhn already said: don't do using namespace std in header files (i assume this code goes in a header file), because otherwise, everyone who includes your header will have using namespace std, and that might lead to unpleasant effects! Unless ... maybe ... if you do it inside your own private namespace.

- No need for a custom copy constructor, the default one will do just fine (as std::vector<bool> will be copied correctly). A rule of thumb: if you need either a custom copy constructor, assignment operator or destructor, you probably need all three of them. Since you don't have a custom destructor nor assignment operator (which is correct because you don't need them), you probably won't need a copy constructor either (which in this case is indeed true).

- std::string has a method 'append' which allows to add one character to the end of the string. So there's not really a need to go around with a std::vector<char>.

- avoid C-style casts, they're ugly and evil. Instead, use static_cast, const_cast and reinterpret_cast to express your intent more clearly.

- and of course, working on single bits is horribly slow, but that one you already know

BTW, have you checked out the GMP library? It has something that might seem very familiar to you http://swox.com/gmp/

Bramz

Originally Posted by .oisyn

monjardin: you are correct . std::vector<bool> is specialized to be stored as actual bits. When referencing a single element in the vector, you won't get a bool& but instead a type that typically holds a reference to the int where that bit is stored, and a bit index in that int. Retrieving or assigning a bool value to this type will read/write the actual bit in the array.

err , are u sure?
in libraries im using there is no special case for std::vector<bool>.
from that what u're saying it looks like single element of std::vector<bool> would consist of two values:
1) reference to where int is stored and
2) bit position in that int.
im sure it isnt done that way, bcos its better to store just actual bool value (1 value) instead two.
it is case of compiler how it stores bool in memory, i.e. old MS Visual-C used int as typedef for bool, while in Visual-C since v6, single byte is used to store boolean value (just use sizeof(bool) to find out how its stored).
of course, difference in size of bool value would cause serious compatibility problems, especially with dynamic libraries, and it causes. thats why i prefer to use some more reliable ways to store true-false states.
furthermore, if one thinks he can conserve some memory by using bool's, think again.

Originally Posted by ikk

err , are u sure?

Yes
http://www.kuzbass.ru/docs/isocpp/li...ib.vector.bool

in libraries im using there is no special case for std::vector<bool>.

That may be, I don't know what libraries you're using, but the standard requires the specialization to be there.

from that what u're saying it looks like single element of std::vector<bool> would consist of two values:
1) reference to where int is stored and
2) bit position in that int.
im sure it isnt done that way, bcos its better to store just actual bool value (1 value) instead two.

No, your assumption is incorrect. Now the standard only requires the bits to be stored "efficently", but a typical implementation uses an array of (unsigned) ints. Whenever you access an element of a non-const vector<bool>, a vector<bool>::reference is constructed and returned, which contains the data needed to reference the right bit in the right int, and you can read and write bool values from/to this object.

furthermore, if one thinks he can conserve some memory by using bool's, think again.

no-one's claiming that here.

hmm, so there really are libraries that has special case for vector<bool>.
i mean, as u're saying, its standard now. but, i dont think that this is advantageous over libs that doesnt has this. bits are most elementary data structures thus creating special functions to access them is nothing good, and i dont like when additional code is packed into my executables.

Originally Posted by ikk

as u're saying, its standard now. but, i dont think that this is advantageous over libs that doesnt has this.

Out of curiosity, what C++ Standard Template Library implementation are you using? Nobody here has claimed it being advantageous..more like the opposite

Originally Posted by ikk

hmm, so there really are libraries that has special case for vector<bool>.
i mean, as u're saying, its standard now. but, i dont think that this is advantageous over libs that doesnt has this.

Well, it's better in terms of memory usage. A non-specialized vector<bool> uses CHAR_BIT (usually 8) times more memory than the specialized vector<bool>. But more importantly, the specialized vector<bool> has a flip method to flip all the bits, and the vector<bool>::reference also has a flip to flip a single bit. So this is correct code:

std::vector<bool> v(3, false); // construct vector with 3 bits set to false
v.flip(); // flip all the bits
v[1].flip(); // flip the second bit

Obviously, this won't compile when you're using a library that doesn't contain a specialized vector<bool>

bits are most elementary data structures thus creating special functions to access them is nothing good, and i dont like when additional code is packed into my executables.

I don't agree that bits are the most elementary data structures from a programmer's point of view, as you can't address individual bits in code. You'll need bitmasks and bitwise operators to access them, which makes them more complicated than say a bool or an int. It's definitely nice to have a class available that abstracts this bitwise mumbo jumbo away from the programmer; most of the methods of such a class will be inlined anyway, and since you'll need to do the bit math yourself when not using such a class anyway, there is no additional code overhead. But the question raised here is whether the specialized vector<bool> is a good one.