title: Bit tricks to find the first position where the number of 0s equals the number of 1s
body: <p>Suppose I have a 32 or 64 bit unsigned integer.</p>
  
  <p>What is the fastest way to find the index i of the leftmost bit such that the number of 0s in the leftmost i bits equals the number of 1s in the leftmost i bits?
  I was thinking of some bit tricks like the ones mentioned <a href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow noreferrer">here</a>.</p>
  
  <p>I am interested in recent x86_64 processor. This might be relevant as some processor support instructions as POPCNT (count the number of 1s) or LZCNT (counts the number of leading 0s).</p>
  
  <p>If it helps, it is possible to assume that the first bit has always a certain value. </p>
  
  <p>Example (with 16 bits):
  If the integer is</p>
  
  <pre><code>1110010100110110b 
           ^ 
           i
  </code></pre>
  
  <p>then i=10 and it corresponds to the marked position.</p>
  
  <p>A possible (slow) implementation for 16-bit integers could be:</p>
  
  <pre><code>mask = 1000000000000000b
  pos = 0
  count=0
  do {
      if(x &amp; mask)
          count++;
      else
          count--;
  
      pos++;
      x&lt;&lt;=1;
  } while(count)
  
  return pos;
  </code></pre>
  
  <p>Edit: fixed bug in code as per @njuffa comment.</p>