title: Intrinsic to count trailing zero bits in 64-bit integers?
body: <p>this is sort of a follow up on some previous questions on bit manipulation.  I modified the code from <a href="http://realtimecollisiondetection.net/blog/?p=78" rel="noreferrer">this site</a> to enumerate strings with K of N bits set (x is the current <code>int64_t</code> with K bits set, and at the end of this code it is the lexicographically next integer with K bits set):</p>
  
  <pre><code>int64_t b, t, c, m, r,z;
  b = x &amp; -x;
  t = x + b;
  c = x^t;
  // was m = (c &gt;&gt; 2)/b per link
  z = __builtin_ctz(x);
  m = c &gt;&gt; 2+z;
  x = t|m;
  </code></pre>
  
  <p>The modification using <code>__builtin_ctz()</code> works fine as long as the least significant one bit is in the lower DWORD of x, but if is not, it totally breaks.  This can be seen with the following code:</p>
  
  <pre><code>for(int i=0; i&lt;64; i++) printf("i=%i, ctz=%i\n", i, __builtin_ctz(1UL &lt;&lt; i));
  </code></pre>
  
  <p>which prints for GCC version 4.4.7:</p>
  
  <pre><code>i=0, ctz=0
  i=1, ctz=1
  i=2, ctz=2
  </code></pre>
  
  <p>...</p>
  
  <pre><code>i=30, ctz=30
  i=31, ctz=31
  i=32, ctz=0
  </code></pre>
  
  <p>or for icc version 14.0.0 something similar (except i>32 gives random results, not zero).  Using division instead of shifting by 2+z works in both cases, but it's about 5x slower on my Sandy Bridge Xeon.  Are there other intrinsics I should be using for 64-bit, or will I have to do some inline assembler?</p>
  
  <p>Thanks!</p>