title: efficiently find the first element matching a bit mask
body: <p>I have a list of <strong>N</strong> 64-bit integers whose bits represent small sets. Each integer has at most <strong>k</strong> bits set to 1. Given a bit mask, I would like to find the first element in the list that matches the mask, i.e. <code>element &amp; mask == element</code>.</p>
  
  <p><strong>Example:</strong></p>
  
  <p>If my list is:</p>
  
  <pre><code>index abcdef
    0   001100
    1   001010
    2   001000
    3   000100
    4   000010
    5   000001
    6   010000
    7   100000
    8   000000
  </code></pre>
  
  <p>and my mask is <code>111000</code>, the first element matching the mask is at index 2.</p>
  
  <p><strong>Method 1:</strong></p>
  
  <p>Linear search through the entire list. This takes O(<strong>N</strong>) time and O(1) space.</p>
  
  <p><strong>Method 2:</strong></p>
  
  <p>Precompute a tree of all possible masks, and at each node keep the answer for that mask. This takes O(1) time for the query, but takes O(2^64) space.</p>
  
  <p><strong>Question:</strong></p>
  
  <p>How can I find the first element matching the mask faster than O(<strong>N</strong>), while still using a reasonable amount of space? I can afford to spend polynomial time in precomputation, because there will be a lot of queries. The key is that <strong>k</strong> is small. In my application, <strong>k</strong> &lt;= 5 and <strong>N</strong> is in the thousands. The mask has many 1s; you can assume that it is drawn uniformly from the space of 64-bit integers.</p>
  
  <p><strong>Update:</strong></p>
  
  <p>Here is an example data set and a simple benchmark program that runs on Linux: <a href="http://up.thirld.com/binmask.tar.gz" rel="noreferrer">http://up.thirld.com/binmask.tar.gz</a>. For <code>large.in</code>, <strong>N</strong>=3779 and <strong>k</strong>=3. The first line is <strong>N</strong>, followed by <strong>N</strong> unsigned 64-bit ints representing the elements. Compile with <code>make</code>. Run with <code>./benchmark.e &gt;large.out</code> to create the true output, which you can then diff against. (Masks are generated randomly, but the random seed is fixed.) Then replace the <code>find_first()</code> function with your implementation.</p>
  
  <p><strong>The simple linear search is much faster than I expected.</strong> This is because <strong>k</strong> is small,  and so for a random mask, a match is found very quickly on average.</p>