Previous power of 2

There is a lot of information on how to find the next power of 2 of a given value (see refs) but I cannot find any to get the previous power of two.

The only way I find so far is to keep a table with all power of two up to 2^64 and make a simple lookup.

• Acius' Snippets
• gamedev
• Bit Twiddling Hacks
• Stack Overflow

Solution 1:

From Hacker's Delight, a nice branchless solution:

uint32_t flp2 (uint32_t 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);
}

This typically takes 12 instructions. You can do it in fewer if your CPU has a "count leading zeroes" instruction.

Solution 2:

uint32_t previous_power_of_two( uint32_t x ) {
    if (x == 0) {
        return 0;
    }
    // x--; Uncomment this, if you want a strictly less than 'x' result.
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x - (x >> 1);
}

Thanks for the responses. I will try to sum them up and explain a little bit clearer. What this algorithm does is changing to 'ones' all bits after the first 'one' bit, cause these are the only bits that can make our 'x' larger than its previous power of two. After making sure they are 'ones', it just removes them, leaving the first 'one' bit intact. That single bit in its place is our previous power of two.

Solution 3:

Probably the simplest approach (for positive numbers):

// find next (must be greater) power, and go one back
p = 1; while (p <= n) p <<= 1; p >>= 1;

You can make variations in many ways if you want to optimize.