title: Efficiently find binary strings with low Hamming distance in large set
body: <p><strong>Problem:</strong></p>
  
  <p>Given a large (~100 million) list of unsigned 32-bit integers, an unsigned 32-bit integer input value, and a maximum <a href="http://en.wikipedia.org/wiki/Hamming_distance" rel="noreferrer">Hamming Distance</a>, return all list members that are within the specified Hamming Distance of the input value.</p>
  
  <p>Actual data structure to hold the list is open, performance requirements dictate an in-memory solution, cost to build the data structure is secondary, low cost to query the data structure is critical.</p>
  
  <p><strong>Example:</strong></p>
  
  <pre><code>For a maximum Hamming Distance of 1 (values typically will be quite small)
  
  And input: 
  00001000100000000000000001111101
  
  The values:
  01001000100000000000000001111101 
  00001000100000000010000001111101 
  
  should match because there is only 1 position in which the bits are different.
  
  11001000100000000010000001111101
  
  should not match because 3 bit positions are different.
  </code></pre>
  
  <p><strong>My thoughts so far:</strong></p>
  
  <p>For the degenerate case of a Hamming Distance of 0, just use a sorted list and do a binary search for the specific input value.</p>
  
  <p>If the Hamming Distance would only ever be 1, I could flip each bit in the original input and repeat the above 32 times.  </p>
  
  <p>How can I efficiently (without scanning the entire list) discover list members with a Hamming Distance > 1.</p>