I am working with bitsets std::bitset<29621645> (i.e. with sizes of 29621645 bits) in C++. Each bitset fills around 29MB, which is a lot.
I fell over a library called sdsl which have their own bitset called sdsl::bit_vector. I was amazed over the low size with same number of bits as above. When I instantiate sdsl::bit_vector (29621645) it's only 3.6 MB. When looking at their code I simply cannot figure out how they are representing such large bitsets with such low memory.
Could someone explain this amazing "trick"?
LINK to code: https://github.com/simongog/sdsl-lite/blob/master/include/sdsl/int_vector.hpp LINK to cheat: http://simongog.github.io/assets/data/sdsl-cheatsheet.pdf
(sidenote: I am aware of not being able to do bitwise operation on the sdsl::bit_vector.)