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.

Are you sure you don't want to round up to a power of two? Taking the nearest one can make your world smaller than you asked for. A larger one can always be trimmed down in the end. — harold, Dec 20 '14 at 18:50
Yes, now when you say it, that sounds like a better way. I'll try to use the answers, and round it up. Thanks! — Daniel Kvist, Dec 20 '14 at 18:52

score 5 · Accepted Answer · answered Dec 20 '14 at 18:49

5

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.

answered Dec 20 '14 at 18:49

harold

61,398
6
86
164

Nice, I missed the fact that we don't actually need to know the log, just the power :) Clean and simple – Niklas B. Dec 20 '14 at 18:55
Actually, I think this was the easiest one. Also, it was easy to use with `int`s. Thanks! – Daniel Kvist Dec 21 '14 at 09:24
How it works? I am unable to get what you are doing here. – Vikas Gupta Apr 04 '16 at 18:54
1

@VikasGupta the shift/or chain in the middle copies the highest set bit to all bits below it. Adding one to it therefore results in the next power of two above the input. To *round* up instead of always going up, one is subtracted in the beginning. – harold Apr 04 '16 at 22:39
This doesn't answer the question correctly. 257 results in 512. The nearest power of 2 is 256. – Pawel Feb 05 '22 at 22:49
@Pawel the code snippet is not the answer. The whole answer is the answer, please read all of it. Calculate the other candidate as well, and *then take the nearest*. – harold Feb 05 '22 at 22:50
@harold fair enough, I multiplied the initial number by 0.8 instead so more likely to upscale than downscale. – Pawel Feb 05 '22 at 23:14

score 4 · Answer 2 · edited May 23 '17 at 12:24

4

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.

edited May 23 '17 at 12:24

Community

1
1

answered Dec 20 '14 at 18:38

Niklas B.

92,950
18
194
224

`^` is the the bitwise XOR operator in java, and not exponentiation as you might expect. – kinbiko Dec 20 '14 at 18:50
@kinbiko Please interpret this answer as mathematical pseudocode, rather than Java – Niklas B. Dec 20 '14 at 18:51
`ceil(log(x))` rounds up? – Daniel Kvist Dec 20 '14 at 19:50
@TheDDestroyer12 yes exactly. – Niklas B. Dec 21 '14 at 01:55
How can I check if a number is a power of two? – Daniel Kvist Dec 21 '14 at 09:10
Also, how can I do it with integers? Eclipse says that `The operator ^ is undefined for the argument type(s) int, double` – Daniel Kvist Dec 21 '14 at 09:17
I checked if the number was power of two by using `if((n & (n - 1)) == 1)`, and I used harolds answer, because I thought it was easier to use with `int`s. Thanks everyone! – Daniel Kvist Dec 21 '14 at 09:37
@TheDDestroyer12 My suggestion for integers was to find the MSB and then go from there, but as harold demonstrated, getting 2^MSB directly is even simpler, so that's what you should do :) By the way, `^` is exponentiation in math, there is no such operator in Java. You would probably use the `pow` function. – Niklas B. Dec 21 '14 at 11:46

Mureinik · Answer 3 · 2017-08-06T14:38:09.547

4

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);

edited Aug 06 '17 at 14:38

answered Dec 20 '14 at 18:45

Mureinik

297,002
52
306
350

score 1 · Answer 4 · answered Dec 04 '16 at 10:14

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.

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

4 Answers4

Guava 20+