Here's an idea

Posted Dec 11, 2007 14:24 UTC (Tue) by jzbiciak (✭ supporter ✭, #5246) [Link]

Keep in mind that a bitvector (sometimes called a bitmap) is something rather different than a bitfield member of a struct or class. Bitvectors have array-like semantics and are quite typically used to represent things such as set membership. (eg. a 1 indicates membership, a 0 indicates lack of membership.) Bitfield members, on the other hand, are scalar quantities. There is no indexing associated with them, and their range is often much more than 0 to 1.

Bitfield members are often useful for storing values with limited range in a compact manner. For example, consider dates and times. The month number only goes from 1-12 and the day number only goes from 1-31. You can store those in 4 and 5 bits respectively. If you store year-1900 instead of the full 4 digit number, you can get by with 7 or 8 bits there. Hours fit in 5 bits, minutes and seconds in 6 bits each. That leads to something like this:

struct packed_time_and_date
{
    unsigned int year   : 7;  /* 7 bits for year - 1900      */
    unsigned int month  : 4;  /* 4 bits for month  (1 - 12)  */
    unsigned int day    : 5;  /* 5 bits for day    (1 - 31)  */
    unsigned int hour   : 5;  /* 5 bits for hour   (0 - 23)  */
    unsigned int minute : 6;  /* 6 bits for minute (0 - 59)  */
    unsigned int second : 6;  /* 6 bits for second (0 - 59)  */
};

Now, if I did my math right, that adds up to 33 bits. Under the x86 UNIX ABI, the compiler will allocate 2 32-bit words for this. The first 5 fields will pack into the first 32-bit word, and the 6th field will be in the lower 6 bits of the second word. That is, sizeof(struct packed_time_and_date) will be 8. If you can manage to squeeze a bit out of the year (say, limit yourself to a smaller range of years), this fits into 32 bits, and sizeof(struct packed_time_and_date) will be 4. In either case, the compiler will update these fields-packed-within-words with an appropriate sequence of loads, shifts, masks, and stores. No C++ or STL necessary.

(If you want to see a more in-depth (ab)use of this facility, check out this source file. It constructs a union of structs, each struct modeling a different opcode space in an instruction set.)

Anyhow, this is what I was referring to as "bit-fields" in the comment you replied to. As you can see, it's rather different than bitvectors. :-)

Bitvectors in C++ and STL have their own problems. I've been reading up on C++ and STL, and vectors of bits apparently have a checkered history in STL. There was one implementation (I believe at SGI) of bitvector (separate of vector<bool>) that didn't make it into the standard, and yet another (apparently a specialization of vector<> especially for bool) that many feel doesn't actually provide proper iterators. I wish I could provide references or details.

All I know is that it's enough for me to avoid STL on bitvectors, and just resort to coding these manually. It's served me well so far. And I don't see a need to invoke generics like sort on them. Something tells me most generic algorithms aren't as interesting on bitvectors. ;-)