Getting the number of trailing 1 bits

Question

Are there any efficient bitwise operations I can do to get the number of set bits that an integer ends with? For example 11₁₀ = 1011₂ would be two trailing 1 bits. 8₁₀ = 1000₂ would be 0 trailing 1 bits.

Is there a better algorithm for this than a linear search? I'm implementing a randomized skip list and using random numbers to determine the maximum level of an element when inserting it. I am dealing with 32 bit integers in C++.

Edit: assembler is out of the question, I'm interested in a pure C++ solution.

Answer 1

Calculate ~i & (i + 1) and use the result as a lookup in a table with 32 entries. 1 means zero 1s, 2 means one 1, 4 means two 1s, and so on, except that 0 means 32 1s.