[Java] Nearest power of 2

As first post I'll write a method to find the "nearest power of 2" starting from an integer in Java: I suppose the number n is bigger than 0 and it is lower than 2^30:

public static int getNearestPowerOfTwoFromBinary(int n){

/*Convert the number in the binary value
then take the first 1 since left: the result is the length
from the right of the number, or the power in decimal*/

String binary = Long.toBinaryString(n);
int power = binary.length() - binary.indexOf("1");
return Math.pow(2, power);
}

There is also another way to calculate the nearest power-of-two number, as the following:

public static int getNearestPowerOfTwo(int n){

//get the power of 2 from n
double powerSinceTwo = Math.log(signal.length)/Math.log(2);

/*if the number is integer than return the number, else return a number
with the power + 1*/

if(powerSinceTwo != Math.floor(powerSinceTwo){
int power = Math.floor(powerSinceTwo) + 1;
return Math.pow(2, power);
}
return n;

}

Why we should find the nearest power of 2 from a number? There are a lot of answers.

Mine is that I needed to use this for a FFT with the Apache Commons Math, because sometimes my signals came with a non-power-of-2 length. Also for JTransforms is usefull to have a full power-of-two signal length to use the multithreaded speed.

But, how to use them to get an array with a power of two length?

public static Object[] getArrayWithPoTLength(Object[] array){

int newLength = getNearestPowerOfTwo(array.length);
Object[] newArray;
if(array.length != newLength){
   newArray = new Object[newLength];
   for(int i=0; i < newLength ; i++){
   if(i < array.length)
      newArray[i] = array[i];
   else
      newArray[i] = new Object();
   }
   return newArray;
}
return array;
}

So, that's all for the first post.
And before you leave, please leave a comment if it was useful or a suggestion to correct something.

Some useful links about: http://www.thatsjava.com/java-programming/253675/

15/03/2012 - Update

Want more? Did you know bitshift operators in Java?
They will give a quick way to find a solution for the problem of this post:

public static int getNearestPowerOfTwoWithShifts(int x){

// return X if it is a power of 2
if ((x & (x-1)) == 0 ) return x;

// integers in java are represented in 32 bits, so:
for(int i=1; i<32; i = i*2){

  x |= ( x >>> i);

}

return x + 1; 
}

So, what's this stuff?
In the first parts your doing a bitwise between X and X-1, so if X is a power of 2, for example 32 its representation in the binary format will be something like:

100000

And X-1 will be something like:

011111

Using the bitwise operator & (AND) the result will be 0.
Otherwise, if we take a non power of 2 number, for example 49 its representation in the binary format is:

110001

And X-1, in the exampe 49 - 1 = 48, is:

110000

So the bitwise result will be something different from 0:

110001 AND 110000 = 110000

We still need to find the nearest power of 2, starting from our X number. Using shift operators in Java we can find them in this way:
Take the number and use the OR operator with shifts, starting with shifting 1 position to all 32 positions...
48 shifted by 1 give back 52.
52 shifted by 2 give back 63.
... and so on until shifting by 32.

Shift by 1: 110001 OR 011000 = 111001

Shift by 2: 111001 OR 001110 = 111111

And so on... until at last we have 63, or 111111.
Now add 1 to this number to obtain a power of 2 number.