Please help me optimize my code for a codechef problem!

I am solving this question on codechef! It is a simple problem, but my solution times out! It seems it is not efficient enough! Please help me optimize it.

Here's the code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) 开发者_JS百科{
            System.out.println((int) (Math.pow(2, (int) ((Math.log(Integer.parseInt(br.readLine()))) / (Math.log(2))))));
        }
    }
} 

regards

shahensha

1. You can cache log(2) in a variable, instead of computing it at every cycle
2. Instead of using Math.log, since you are working with integers, you can compute log2 by using Integer.numberOfLeadingZeros (see the docs), as ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)

The numberOfLeadingZeros should be quite fast, as the source code reveals that it just does a few bit-level operations to perform its work.

Is this to find the next lower power of 2? There are way faster ways to do that than calling any log functions, such as various bit tricks. In general in 2's complement representation, the next lower power of 2 of positive x is the same as x with only x's most significant bit set, and all other bits zero.

Edit: since you've confirmed you're looking for the next lower power of two, here's the canonical (branchless) bit hack:

/** The largest power of 2 <= x.
    Only valid for positive numbers. */
static int nextLowerPowerOf2(int x) {
    x >>>= 1;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x++;
    return x;
}

It's a contest and you ask for help?? How can you be proud of you if the solution doesn't come from you?

Anyway, here is some hints:

1. Optimize your loop with pre-calculated values: Math.log(2) always give the same answer!
2. Use a StringBuffer in your loop and print only once, after the loop (to verify if it improve performance)
3. Math.Pow(2, INT), try with a Bitshift instead of Pow :)

[EDITED] My previous solution about Math.Pow was wrong, thanks Andrea