🚀 go-pugleaf

An elegant and efficient MSB-finding algorithm has been forwarded to me by
Dean Inada (dmi@peregrine.com). It has a constant running time proportional
to Log2(machine int size):

>msbpos(i)
>    {
>    int p = 0;
>    if (i & 0xAAAAAAAA  >  i &  0x55555555    ) p++;
>    if (i & 0xCCCCCCCC  >  i &  0x33333333    ) p += 2;
>    if (i & 0xF0F0F0F0  >  i &  0x0f0f0f0f    ) p += 4;
>    if (i & 0xFF00FF00  >  i &  0x00ff00ff    ) p += 8;
>    if (i & 0xFFFF0000  >  0 /* 0x0000xxxx */ ) p += 16;
>    return(p);

The recursive derivation is not immediately obvious but resembles priority
encoder designs. The logical bit-sieve takes advantage of arithmetic inequality
of two integers A, B: if A >= B then msbpos(A) >= msbpos(B), though note that
exact equality '=' may not replace the '>='. A companion "lsbpos" routine bit
reverses its input then continus with msbpos(). Bit reversal hardware is common
on machines designed to support the FFT.

    /Alan Paeth