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