Low Order Zero Counter

Warning: This is perhaps the ugliest code on my site.

If 0≤p<31 then fb(2p) = p.

(The value 0x12CF8DD4 is a shift register sequence for GF(32). It and the table are computed here. The irreducible polynomial was chosen from those listed by this Scheme program that runs in this framework.)

A positive integer may be expressed uniquely as p = (2k+1)2n with non negative k and n.
Given p < 231 , 2n = g(p) = ((p^(p-1))+1)>>1 in C syntax.

Composing functions g and bf, fb(g(n)) counts the number of low order zeros in a 31 bit integer n.

Depending on machine instruction set this is as few as 7 instructions with no branches. The performance will be dominated on some machines by multiply.

Here is similar code with advantages and disadvantages.