Computing Trailing Zeros (2009)

Computing Trailing Zeros (2009)

Let’s have an example: a binary number of length 8 = 23 is a de Bruijn sequence, if it contains every possible bitstring of length 3, i.e. 000, 001, 010, 011, and so on. Now, in order to compute the number of trailing zeros of a binary, we need a de Bruijn sequence of exactly the size of our binary, i.e. CHAR_BITS*sizeof(int). Actually, this is how left-shifting is formally defined: Of course, no sane chip designer will use multiplication in order to implement bit shifts on a new CPU, but this trick will help us determine the number of trailing zeros in a binary.

Source: 7ooo.mooo.com