How to find the closest number, that is, the strength of two, to another number?
I am creating a world generator for my 2D game in which Diamond Square Algorithm in Java and I heard that it only works (or at least only works well) with numbers that are 2 n +1 (power of two) ...
The method that generates the world is called with generateWorld(width, height)
, but this creates a problem. I want to be able to enter width
and the function will find the nearest numberequal to two if there is no input signal width. I really don't know how I can go about doing this, so all help is greatly appreciated!
Summing up . If one number is not equal to two, I want to find the closest number to it, which is is equal to two.
source to share
You can round up to the higher cardinality of two (no change if it was already two):
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 the two does not exist.
Another candidate is only half of that. Then take the closest one.
source to share
There are two candidates: 2^floor(log2(x))
and 2^ceil(log2(x))
. Just check which one is closer.
For integers, you can use bit scripting to find the most significant set of bits to get the exact value floor(log2(x))
. I've written about this before . Again, this gives you two candidates that you can check.
source to share
Mathematically speaking, the closest power of 2 would be 2 round (log 2(x)) . Java unfortunately does not have a pre-prepared method for the log 2, but fortunately, it is easily implementable with the pre-existing functions java.lang.Math
:
int width = ...;
double log = Math.log(width) / Math.log(2);
long roundLog = Math.round(log);
long powerOfTwo = Math.pow(2, roundLog);
source to share
Guava 20 +
You have 3 useful methods:
-
IntMath.ceilingPowerOfTwo(x)
-
IntMath.floorPowerOfTwo(x)
-
IntMath.isPowerOfTwo(x)
and you can check which of the floor levels is 2 and the max power of 2 is closer.
eg:.
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 IntMath
not enough.
source to share