title: Bloom filter with bitwise operations in python
body: <p>Consider the following Python implemetation for the <a href="https://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">bloom filter</a>:</p>
  
  <pre><code>class BloomFilter(object):
      """A simple bloom filter for lots of int/str"""
  
      def __init__(self, array_size=(1 * 1024), hashes=13):
          """Initializes a BloomFilter() object:
              Expects:
                  array_size (in bytes): 4 * 1024 for a 4KB filter
                  hashes (int): for the number of hashes to perform"""
  
          self.filter = bytearray(array_size)     # The filter itself
          self.bitcount = array_size * 8          # Bits in the filter
          self.hashes = hashes                    # The number of hashes to use
  
      def _hash(self, value):
          """Creates a hash of an int and yields a generator of hash functions
          Expects:
              value: int()
          Yields:
              generator of ints()"""
  
          # Build an int() around the sha256 digest of int() -&gt; value
          value = value.__str__() # Comment out line if you're filtering strings()
          digest = int(sha256(value).hexdigest(), 16)
          for _ in range(self.hashes):
              yield digest &amp; (self.bitcount - 1)
              digest &gt;&gt;= (256 / self.hashes)
  
      def add(self, value):
          """Bitwise OR to add value(s) into the self.filter
          Expects:
              value: generator of digest ints()
          """
          for digest in self._hash(value):
              self.filter[(digest / 8)] |= (2 ** (digest % 8))
  
  
      def query(self, value):
          """Bitwise AND to query values in self.filter
          Expects:
              value: value to check filter against (assumed int())"""
          return all(self.filter[(digest / 8)] &amp; (2 ** (digest % 8)) 
              for digest in self._hash(value))
  </code></pre>
  
  <p>A simple use of this bloom filter would be:</p>
  
  <pre><code>bf = BloomFilter()
  
  bf.add(30000)
  bf.add(1230213)
  bf.add(1)
  
  print("Filter size {0} bytes").format(bf.filter.__sizeof__())
  print bf.query(1) # True
  print bf.query(1230213) # True
  print bf.query(12) # False
  </code></pre>
  
  <p>Can you explain <strong>in detail</strong> how the hash functions are used? For example in the line:</p>
  
  <pre><code>self.filter[(digest / 8)] |= (2 ** (digest % 8))
  </code></pre>
  
  <p>it seems that the code is using <code>OR</code> and <code>AND</code> operations to write to the filter using the hash functions created using <code>self._hash</code> but I cannot understand how this bitwise operation works when adding and querying values to/from the filter.</p>
  
  <ul>
  <li>Why the <code>2**(digest %8)</code>?</li>
  <li>Why the use of <code>OR</code> to write to the filter and <code>AND</code> to query?</li>
  </ul>