If I have a number a, I want the value of x in b=2^x, where b is the next power of 2 greater than a.
In case you missed the tag, this is Java, and a is an int. I'm looking for the fastest way to do this. My solution thusfar is to use bit-twiddling to get b, then do (int)(log(b)/log(2)), but I feel like there has to be a faster method that doesn't involve dividing two floating-point numbers.
just do the following:
extract the highest bit by using this method (modified from hdcode):
int msb(int x) {
if (pow2(x)) return x;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x | (x >> 24);
return x - (x >> 1);
}
int pow2(int n) {
return (n) & (n-1) == 0;
}
combining both functions into this function to get a number 'b', that is the next power of 2 of a given number 'a':
int log2(int x) {
int pow = 0;
if(x >= (1 << 16)) { x >>= 16; pow += 16;}
if(x >= (1 << 8 )) { x >>= 8; pow += 8;}
if(x >= (1 << 4 )) { x >>= 4; pow += 4;}
if(x >= (1 << 2 )) { x >>= 2; pow += 2;}
if(x >= (1 << 1 )) { x >>= 1; pow += 1;}
return pow;
}
kind regards, dave