Fastest way to enumerate through turned on bits of an integer

Question

What's the fastest way to enumerate through an integer and return the exponent of each bit that is turned on? Have seen an example using << and another using Math.Pow. Wondering if there is anything else that's really fast.

Thanks.

Answer 1

The fastest way? Lookup tables are almost always the fastest way. Build an int[][] array with four billion entries, one for each int, containing an array of the numbers you want. Initializing the table will take some time, of course but the lookups will be incredibly fast.

I note that you have not said what "fastest" means with sufficient precision for anyone to actually answer the question. Does it mean fastest amortized time including startup time, or marginal lookup time assuming that startup costs can be neglected? My solution sketch assumes the latter.

Obviously a 32 bit machine with 2 billion bytes of address space will not have enough address space to store thirty billion bytes of arrays. Get yourself a 64 bit machine. You'll need at least that much physical memory installed as well if you want it to be fast -- the paging is going to kill you otherwise.

I sure hope the couple of nanoseconds you save on every lookup are worth buying all that extra hardware. Or maybe you don't actually want the fastest way?

:-)

Answer 2

I imagine bit-shifting would be the fastest. Untested, but I think the following ought to be fast (as fast as IEnumerables are at least).

IEnumerable<int> GetExponents(Int32 value)
{
    for(int i=0; i<32; i++)
    {
        if(value & 1)
            yield return i;
        value >>= 1;
    }
}

If you want it to be faster, you might consider returning a List<int> instead.

Answer 3

The IEnumerable is not going to perform. Optimization of some examples in this topic:

First one (fastest - 2.35 seconds for 10M runs, range 1..10M):

static uint[] MulDeBruijnBitPos = new uint[32] 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

static uint[] GetExponents(uint value)
{
    uint[] data = new uint[32];
    int enabledBitCounter = 0;

    while (value != 0)
    {
        uint m = (value & (0 - value));
        value ^= m;
        data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27];
    }

    Array.Resize<uint>(ref data, enabledBitCounter);
    return data;
}

Another version (second fastest - 3 seconds for 10M runs, range 1..10M):

static uint[] GetExponents(uint value)
{
    uint[] data = new uint[32];
    int enabledBitCounter = 0;

    for (uint i = 0; value > 0; ++i)
    {
        if ((value & 1) == 1)
            data[enabledBitCounter++] = i;
        value >>= 1;
    }

    Array.Resize<uint>(ref data, enabledBitCounter);
    return data;
}