Accname
2D-Graphics enthusiast
- Reaction score
- 1,462
Hi guys, just wanted to share with you 2 very useful and ingenious algorithms which i found across the interwebs.
The first one checks if a given integer number is a power of two:
Its incredibly fast and effective and i love the solution. The best i have ever seen in fact.
The algorithm checks the number of "1's" in the binary representation of value.
To do this the algorithm calculates the two-complement of the value and connects them with a logic AND.
Only if value has only a single 1 in its binary representation this method will return true.
The next algorithm calculates the next biggest power of two for a given integer:
As far as i understood this algorithm finds the highest 1 in the binary representation of value, then makes every position in the binary representation, which comes before the highest 1, a 1 as well.
Then, when we add 1 at the end, all the 1's in binary will become a zero exept for the next highest position which has been a zero before.
This is really complicated to explain, its best to try it oneself with an example value.
Lets say we take the value 5, in binary represented as 0101.
Now we sutract 1 and get 0100. # value--;
we shift 0100 one position to the right and OR the result with 0100 => 0110 # value |= value >> 1;
we shift 0110 two positions to the right and OR the result with 0110 => 0111 # value |= value >> 2;
we shift 0110 four positions to the right and OR the result with 0110 => 0111 # value |= value >> 4;
we shift 0110 eight positions to the right and OR the result with 0110 => 0111 # value |= value >> 8;
we shift 0110 sixteen positions to the right and OR the result with 0110 => 0111 # value |= value >> 16;
We now add 1 to the result and get: 0111 + 1 = 1000 = 8
Just wanted to share these 2 gems with you guys.
The first one checks if a given integer number is a power of two:
Code:
private boolean is_power_of_two(int value){
return (value & (~value + 1)) == value;
}
The algorithm checks the number of "1's" in the binary representation of value.
To do this the algorithm calculates the two-complement of the value and connects them with a logic AND.
Only if value has only a single 1 in its binary representation this method will return true.
The next algorithm calculates the next biggest power of two for a given integer:
Code:
private int next_power_of_two(int value){
value--;
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value++;
return value;
}
Then, when we add 1 at the end, all the 1's in binary will become a zero exept for the next highest position which has been a zero before.
This is really complicated to explain, its best to try it oneself with an example value.
Lets say we take the value 5, in binary represented as 0101.
Now we sutract 1 and get 0100. # value--;
we shift 0100 one position to the right and OR the result with 0100 => 0110 # value |= value >> 1;
we shift 0110 two positions to the right and OR the result with 0110 => 0111 # value |= value >> 2;
we shift 0110 four positions to the right and OR the result with 0110 => 0111 # value |= value >> 4;
we shift 0110 eight positions to the right and OR the result with 0110 => 0111 # value |= value >> 8;
we shift 0110 sixteen positions to the right and OR the result with 0110 => 0111 # value |= value >> 16;
We now add 1 to the result and get: 0111 + 1 = 1000 = 8
Just wanted to share these 2 gems with you guys.