I have a requirement to compute the greatest power of 2 which is < an integer value, x
currently I am using:
#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)
x = round(pow(2,(ceil(log2(n))-1)));
this is in a performance critical function
Is there a more computationally efficient way of calculating x?
You are essentially looking for the highest non-zero bit in your number. Many processors have built-in instructions for this, which in turn are exposed by many compilers. For example, in GCC I would look at __builtin_clz, which
Returns the number of leading 0-bits in
x, starting at the most significant bit position.
Together with sizeof(int) * CHAR_BIT and a shift, you can use this to figure out the corresponding pure-power-of-two integer. There's also a version for long integers.
(The CPU instruction is presumably called "CLZ" (count leading zeros), in case you need to look this up for other compilers.)
Based on Bit Twiddling Hacks: Find the log base 2 of an N-bit integer in O(lg(N)) operations by Sean Eron Anderson (code contributed by Eric Cole and Andrew Shapira):
unsigned int highest_bit (uint32_t v) {
unsigned int r = 0, s;
s = (v > 0xFFFF) << 4; v >>= s; r |= s;
s = (v > 0xFF ) << 3; v >>= s; r |= s;
s = (v > 0xF ) << 2; v >>= s; r |= s;
s = (v > 0x3 ) << 1; v >>= s; r |= s;
return r | (v >> 1);
}
This returns the index of the highest bit of the input; the greatest power of 2 no greater than the input is then 1 << highest_bit(x), and the greatest power of 2 strictly less than the input is thus simply 1 << highest_bit(x-1).
For 64-bit inputs, just change the input type to uint64_t and add the following extra line at the beginning of the function, after the variable declarations:
s = (v > 0xFFFFFFFF) << 8; v >>= s; r |= s;
I have an integer log2 function in my c-libutl library (hosted on googlecode if anyone is interested)
/*
** Integer log base 2 of a 32 bits integer values.
** llog2(0) == llog2(1) == 0
*/
unsigned short llog2(unsigned long x)
{
long l = 0;
x &= 0xFFFFFFFF /* just in case 'long' is more than 32bit */
if (x==0) return 0;
#ifndef UTL_NOASM
#if defined(__POCC__) || defined(_MSC_VER) || defined (__WATCOMC__)
/* Pelles C MS Visual C++ OpenWatcom */
__asm { mov eax, [x]
bsr ecx, eax
mov l, ecx
}
#elif defined(__GNUC__)
l = (unsigned short) ((sizeof(long)*8 -1) - __builtin_clzl(x));
#else
#define UTL_NOASM
#endif
#endif
#ifdef UTL_NOASM /* Make a binary search.*/
if (x & 0xFFFF0000) {l += 16; x >>= 16;} /* 11111111111111110000000000000000 */
if (x & 0xFF00) {l += 8; x >>= 8 ;} /* 1111111100000000*/
if (x & 0xF0) {l += 4; x >>= 4 ;} /* 11110000*/
if (x & 0xC) {l += 2; x >>= 2 ;} /* 1100 */
if (x & 2) {l += 1; } /* 10 */
return l;
#endif
return (unsigned short)l;
}
Then you can simply compute
(1 << llog2(x))
to compute the greatest power of two that is less than x. Beware 0! You should handle it separately.
It uses assembler code but can also be forced to plain C code by defining the UTL_NOASM symbol.
The code has been tested at the time but it's quite some time I don't use it and I can't say if it behaves in a 64-bit environment.
Shifting bits around will most likely be much faster. Probably some bisection method on bits could make it even faster. Nice exercise for an improvement.
#include <stdio.h>
int closestPow2(int x)
{
int p;
if (x <= 1) return 0; /* No such power exists */
x--; /* Account for exact powers of 2, then one power less must be returned */
for (p = 0; x > 0; p++)
{
x >>= 1;
}
return 1<<(p-1);
}
int main(void)
{
printf("%x\n", closestPow2(0x7FFFFFFF));
return 0;
}
Left and right shift operators do this the best
int MaxPowerOf2(int x)
{
int out = 1;
while(x > 1) { x>>1; out<<1;}
return out;
}
#include <math.h>
double greatestPower( double x )
{
return floor(log( x ) / log( 2 ));
}
That is true since log in monotony increasing function.