🚀 go-pugleaf

Given a 'very sparse' integer having only one bit set in position 'p', this
C fragment detects 'very sparseness' and returns p. It is based on two entries
appearing in _Graphics Gems II_ (Academic Press, 1992, ed: Jim Arvo). These
describe integer operations combining bitwise-logic and arithmetic to perform
sparesness tests, bit tallying, etc. (The two entries are by Ken Shoemake and
Alan Paeth; I've forgotten their exact titles).

int sparsebit(i)
    long i;
    {
    int p;
    p = 0;
/* return position 'p' on range [0..31] of a "lone bit" integer (value 2^p) */
/* otherwise, return -1. This is "little-Endian form" as the lsb is at p=0. */
    if (i == 0) return(-1);		/* no bits set */
    if ((i & (-i)) != i) return(-1);	/* two or more bits set */
    if (i & 0xAAAAAAAA) p++;
    if (i & 0xCCCCCCCC) p += 2;
    if (i & 0xF0F0F0F0) p += 4;
    if (i & 0xFF00FF00) p += 8;
    if (i & 0xFFFF0000) p += 16;
    return(p);
    }


The msb of a sparse word having any number of bits set can be found by using:

int msbbit(i)
    long i;
    {
    long i2;
/* return the bit position of the msb as [0..31]; return -1 on arg of zero */
    while (i2 = (i & (-i)) i = i2;
    return(sparsebit(i));
    }

which removes the set bits (if any) having least weight until merely the msb
remains and then invokes the first subroutine. (This is described in the second
Gem). Note that the first algorithm has worse-case running time which grows
by log2(W) for world length W: 32-bit longs and especially 64-bit longs are big
wins. The bit-discard loop of the second procedure has run time proportional to
the number of 'on' bits in the input. Its worst-case running time occurs when
called with an input of -1 (W passes through the loop).

When non-sparse input is anticipated the stock shift-and-test or byte-table
methods give much better average-case performance. In these cases msbbit()
can be sped up significantly with simple heuristics. For instance, a prefacing

    if (i < 0) return(-1);

in msbbit() gives fast returns for 50% of its input, including the worst case.

   /Alan Paeth