power_of_two function

Originally Posted by CornedBee

Haven't validated the theory behind this, but it should work:

Code:

unsigned power_of_two(unsigned i) {
  while(i & (i-1))
    i &= i-1;
  return i;
}

That's an interesting solution which appears to work correctly, returning a power of two not greater than the input.

Originally Posted by CornedBee

Of course, if we're at that low level, it's easier to do this:

Code:

return 1 << (sizeof(unsigned)*CHAR_BIT - 1) - clz(i)

where clz is the count leading zeros instruction many architectures have. x86 has BSF, bit scan forward. Its performance over time has varied greatly in various CPUs, but as of the Core2, it's fast again, and will easily beat every loop.

I totally forgot to mention that instruction though I did think of it when I started writing my first post. I figured there'd be an intrinsic for it now.

Code:

unsigned power_of_two(unsigned i) {
  while(i & (i-1))
    i &= i-1;
  return i;
}

very nice!
i do think the modified brewbuck solution will be faster (fewer iterations) if i is often a random (half the bits set) number between 2^21 and 2^32 (or is > 2^16 but for some reason will have all or most bits set).

Originally Posted by CornedBee

x86 has BSF, bit scan forward. Its performance over time has varied greatly in various CPUs, but as of the Core2, it's fast again, and will easily beat every loop.

I was going to mention BSF/BSR. I used those instructions recently to implement a 1M entry bitmap with constant time lookup of the first non-zero bit -- on my machine, it could search a 1M bit array for the first non-zero bit in under 22 nanoseconds.

Of course, BSF isn't enough on its own to get that speed -- I used a hierarchical data structure to accelerate the search to constant time.

EDIT: here's code to do it using gcc:

Code:

unsigned int power_of_two(unsigned int max)
{
    int bit;
    __asm__("bsr %1, %0" : "=g" (bit) : "g" (max));
    return 1 << bit;
}

That's an interesting solution which appears to work correctly, returning a power of two not greater than the input.

That depends on what the original poster really wants.

Different people have posted different solution sets.

One set of solutions always returns a power of two less than the target value.

One set of solutions always returns a power of two less than or equal to the target value.

very nice! i do think the modified brewbuck solution will be faster if i is often a random number between 2^21 and 2^32.

Try the `power_of_twoe' function below with the code provided by CornedBee.

Depending on your processor, with an expected uniform distribution, it will be at least as fast as the code provided by iMalc.

Depending on your processor, with an expected uniform distribution, you can use the `power_of_twoe' function below with a 256 byte table and it will be at least as fast as the code provided by iMalc.

Soma

Code:

unsigned int power_of_twoe
(
    unsigned int i
)
{
    int l(i & (i-1));
    if(!l)
    {
        return(i >> 1);
    }
    if((1 << 16) > i)
    {
        if((1 << 8) > i)
        {
            return(power_of_two(i));
        }
        return(power_of_two(i >> 8) << 8);
    }
    if((1 << 24) > i)
    {
        return(power_of_two(i >> 16) << 16);
    }
    return(power_of_two(i >> 24) << 24);
}

Also, check out this cool list of bit hacks:

Bit Twiddling Hacks