How to find the nearest number, that is power of two, to another number?

Question

I'm creating a world generator for my 2D game, which uses the Diamond-Square Algorithm in Java, and I've heard that it only works (or at least, only works well) with numbers that are 2ⁿ+1 (power of two).

The method that generates the world is called with generateWorld(width, height), but that creates a problem. I want to be able to input a width, and the function will find the nearest number which is a power of two, if the input width isn't. I don't really know how I can do this, so all help is greatly appreciated!

Summarizing: If one number isn't power of two, I want to find the nearest number to that one, which is a power of two.

Answer 1

You can round up to a higher power of two (no change if it already was a power of two) like this:

x = x - 1;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x + 1;

It will give 0 for inputs where the next higher power of two does not exist.

The other candidate is simply half that. Then take the nearest.

Answer 2

There are two candidates: 2^floor(log2(x)) and 2^ceil(log2(x)). Just check which of the two is closer.

For integers, you can use bit fiddling to find the most-significant set bit to get the exact value of floor(log2(x)). I've written about the idea before. Again this yields two candidates that you can check.

Answer 3

Mathematically speaking, the closest power of 2 would be 2^{round(log₂(x))}. Java, unfortunately, doesn't have a pre-made method for log₂, but luckily, it's easily doable with the pre-existing java.lang.Math functions:

int width = ...;
double log = Math.log(width) / Math.log(2);
long roundLog = Math.round(log);
long powerOfTwo = Math.pow(2, roundLog);

Answer 4

Guava 20+

You have 3 useful methods:

• IntMath.ceilingPowerOfTwo(x)
• IntMath.floorPowerOfTwo(x)
• IntMath.isPowerOfTwo(x)

and you can check which one of the floor power of 2 and the ceiling power of 2 is closer.

E.g.:

public static void main(String[] args) {
    for ( int i = 1 ; i < 13 ; i++ ) {
        nearestPowerOfTwo(i);
    }
}

private static void nearestPowerOfTwo(int x) {
    int ceil = IntMath.ceilingPowerOfTwo(x);
    int floor = IntMath.floorPowerOfTwo(x);
    System.out.print(x + " ---> ");
    if ( IntMath.isPowerOfTwo(x) ) {
        System.out.println(x + " (the number is power of 2)");
    } else if ( ceil - x > x - floor ) {
        System.out.println(floor);
    } else if (ceil - x == x - floor) {
        System.out.println(floor + " and " + ceil);
    } else {
        System.out.println(ceil);
    }
}

Output:

1 ---> 1 (the number is power of 2)
2 ---> 2 (the number is power of 2)
3 ---> 2 and 4
4 ---> 4 (the number is power of 2)
5 ---> 4
6 ---> 4 and 8
7 ---> 8
8 ---> 8 (the number is power of 2)
9 ---> 8
10 ---> 8
11 ---> 8
12 ---> 8 and 16

There are also LongMath and DoubleMath if the IntMath is not enough.