title: Efficient execution of boolean expression on bitmap in C or C++
body: <p>What is the most efficient way of executing a boolean expression on a bitmap in C or C++? For example, let's say that I have a 4-bit bitmap <code>(a, b, c, d)</code>. Now, let's say that I have a simple boolean expression like <code>(a AND b) OR (c AND d)</code>. How should I represent the boolean expression so that I could efficiently apply it to my bitmap? I am looking for a generic solution that can be applied to any boolean expression, not just the one given as example. In other words, I am looking for some way to "compile" the boolean expression into another data structure that could be used to efficiently reduce my bitmap into a boolean.</p>
  
  <p>The bitmap structure is the result of filtering operations on the records of a database. Every record has its own bitmap, and every bit in a bitmap is the result of an individual filtering rule. The boolean expression is used to combine these filtering rules to decide whether the record should be included in the results of a database query. There can be up to 64 individual filtering rules that can be combined by the boolean operation, hence the bitmap can be represented as an <code>unsigned long long int</code> if necessary.</p>
  
  <p>The solution should be efficient in terms of speed and should not alter the bitmap structure. The conversion of the boolean expression into another structure does not have to be memory-efficient nor fast, because it can be cached (at least in my current use case). The reducing of the bitmap with the transformed boolean expression should be both fast and memory efficient.</p>
  
  <p><strong>Notes:</strong></p>
  
  <ul>
  <li>The boolean expression is only using nested AND and OR operations (no
  IF statements).</li>
  <li>The solution should assume the availability of a 64bit CPU.</li>
  <li>The solution should not be CPU-dependent (beside 64bit addressing).</li>
  <li>The solution should not assume the availability of any other particular hardware (<em>eg</em> GPU).</li>
  <li>All the bitmaps are in memory.</li>
  <li>There can be a very large number of bitmaps (billions).</li>
  <li>Bitmaps are updated one at a time.</li>
  </ul>