Tuesday, April 16, 2013

How to Find the nearest power of 2


/* returns greatest power of 2 less than or equal to x, branch-free */

int
flp2(int x)
{
    x = x | (x>>1);
    x = x | (x>>2);
    x = x | (x>>4);
    x = x | (x>>8);
    x = x | (x>>16);
    return x - (x>>1);
}
It's entertaining to study it and see how it works. I think the only way for you to know for sure which of the solutions you see will be optimal for your situation is to use all of them in a text fixture and profile it and see which is most efficient for your purpose.
Being branch-free, this one is likely to be quite good performance-wise relative to some others, but you should test it directly to be sure.
If you want the least power of two greater than or equal to X, you can use a slightly different solution:
unsigned
clp2(unsigned x)
{
    x = x -1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x + 1;
}

No comments:

Post a Comment