Find which power of 2 range a number falls within? (In C)

Question

As in whether it falls within 2^3 - 2^4, 2^4 - 2^5, etc. The number returned would be the EXPONENT itself (minus an offset).

How could this be done extremely quickly and efficiently as possible? This function will be called a lot in a program that is EXTREMELY dependent on speed. This is my current code but it is far too inefficient as it uses a for loop.

static inline size_t getIndex(size_t numOfBytes)
{
    int i = 3;
    for (; i < 32; i++) 
    {
        if (numOfBytes < (1 << i)) 
            return i - OFFSET;
    }
    return (NUM_OF_BUCKETS - 1);
}

Thank you very much!

Answer 1

What you're after is simply log₂(n), as far as I can tell.

It might be worth cheating and using some inline assembly if your target architecture(s) have instructions that can do this. See the Wikipedia entry on "find first set" for lots of discussion and information about hardware support.

Answer 2

One way to do it would be to find the highest order bit that is set to 1. I'm trying to think if this is efficient though, since you'll still have to do n checks in worst case.

Maybe you could do a binary search style where you check if it's greater than 2^16, if so, check if it's greater than 2^24 (assuming 32 bits here), and if not, then check if it's greater than 2^20, etc... That would be log(n) checks, but I'm not sure of the efficiency of a bit check vs a full int comparison.

Could get some perf data on either.