title: How to build N bits variables in C++?
body: <p>I am dealing with very large list of booleans in C++, around 2^N items of N booleans each. Because memory is critical in such situation, i.e. an exponential growth, I would like to build a N-bits long variable to store each element.</p>
  
  <p>For small N, for example 24, I am just using <code>unsigned long int</code>. It takes 64MB ((2^24)*32/8/1024/1024). But I need to go up to 36. The only option with build-in variable is <code>unsigned long long int</code>, but it takes 512GB ((2^36)*64/8/1024/1024/1024), which is a bit too much.
  With a 36-bits variable, it would work for me because the size drops to 288GB ((2^36)*36/8/1024/1024/1024), which fits on a node of my supercomputer.</p>
  
  <p>I tried <code>std::bitset</code>, but <code>std::bitset&lt; N &gt;</code> creates a element of at least 8B.
  So a list of <code>std::bitset&lt; 1 &gt;</code> is much greater than a list of <code>unsigned long int</code>.
  It is because the <code>std::bitset</code> just change the representation, not the container.</p>
  
  <p>I also tried <code>boost::dynamic_bitset&lt;&gt;</code> from Boost, but the result is even worst (at least 32B!), for the same reason.</p>
  
  <p>I know an option is to write all elements as one chain of booleans, 2473901162496 (2^36*36), then to store then in 38654705664 (2473901162496/64) <code>unsigned long long int</code>, which gives 288GB (38654705664*64/8/1024/1024/1024). Then to access an element is just a game of finding in which elements the 36 bits are stored (can be either one or two). But it is a lot of rewriting of the existing code (3000 lines) because mapping becomes impossible and because adding and deleting items during the execution in some functions will be surely complicated, confusing, challenging, and the result will be most likely not efficient.</p>
  
  <p>How to build a N-bits variable in C++?</p>