BitTwiddle - Your daily bit twiddle fortune.
       
       ___[ Contribute ]
       Want to share your BitTwiddles?
 (HTM) Show them to use on irc.bitreich.org/#bitreich-en!
       
       ___[ Twiddle ]
       
       Count the consecutive zero bits (trailing) on the right linearly
       
       unsigned int v;  // input to count trailing zero bits
       int c;  // output: c will count v's trailing zero bits,
               // so if v is 1101000 (base 2), then c will be 3
       if (v)
       {
         v = (v ^ (v - 1)) >> 1;  // Set v's trailing 0s to 1s and zero rest
         for (c = 0; v; c++)
         {
           v >>= 1;
         }
       }
       else
       {
         c = CHAR_BIT * sizeof(v);
       }
       
       The average number of trailing zero bits in a (uniformly distributed) random
       binary number is one, so this O(trailing zeros) solution isn't that bad compared
       tto the faster methods below.
       
       Jim Cole suggested I add a linear-time method for counting the trailing zeros on
       August 15, 2007. On October 22, 2007, Jason Cunningham pointed out that I had
       neglected to paste the unsigned modifier for v. %
       
       Count the consecutive zero bits (trailing) on the right in parallel
       
       unsigned int v;      // 32-bit word input to count zero bits on right
       unsigned int c = 32; // c will be the number of zero bits on the right
       v &= -signed(v);
       if (v) c--;
       if (v & 0x0000FFFF) c -= 16;
       if (v & 0x00FF00FF) c -= 8;
       if (v & 0x0F0F0F0F) c -= 4;
       if (v & 0x33333333) c -= 2;
       if (v & 0x55555555) c -= 1;
       
       Here, we are basically doing the same operations as finding the log base 2 in
       parallel, but we first isolate the lowest 1 bit, and then proceed with c
       starting at the maximum and decreasing. The number of operations is at most 3 *
       lg(N) + 4, roughly, for N bit words.
       
       Bill Burdick suggested an optimization, reducing the time from 4 * lg(N) on
       February 4, 2011.
       
       ================================
       
       The twiddles are from various sources. See:
 (DIR) Fortune twiddles.
 (DIR) Twiddle scripts.
       
 (DIR) << back to bitreich.org