The standard, for best intentions, decided that vector<bool>
should be specialized to be implemented as a bitset.
A bit-set is fast enough, and you have the choice also of std::bitset which is fixed size, and boost::dynamic_bitset
of which the size is runtime defined, and is built on top of vector<unsigned int>
anyway (It may be a template on what integral type is used).
There is no point optimising further to save you some bit-twiddling so the suggestion would be to use one of these.
By the way, I have seen a "scattered" bitmap, whereby if the value falls within a certain range it uses one, otherwise it will use a tree-style lookup. (This technique can also be used for Z-table (normal distribution CDF type) functions where you "cache" the table in memory for up to 95% or 99% of the density and use the slow-calculation for the extreme values (and I once actually had to do that).