How can I test whether a number is a power of 2?
I need a function like this:
// return true if 'n' is a power of 2, e.g.
// is_power_of_2(16) => true
// is_power_of_2(3) => false
bool is_power_of_2(int n);
Can anyone suggest how I could write this?
(n & (n - 1)) == 0 is best. However, note that it will incorrectly return true for n=0, so if that is possible, you will want to check for it explicitly.
http://www.graphics.stanford.edu/~seander/bithacks.html has a large collection of clever bit-twiddling algorithms, including this one.
A power of two will have just one bit set (for unsigned numbers). Something like
bool powerOfTwo = !(x == 0) && !(x & (x - 1));
Will work fine; one less than a power of two is all 1s in the less significant bits, so must AND to 0 bitwise.
As I was assuming unsigned numbers, the == 0 test (that I originally forgot, sorry) is adequate. You may want a > 0 test if you're using signed integers.
Powers of two in binary look like this:
1: 0001
2: 0010
4: 0100
8: 1000
Note that there is always exactly 1 bit set. The only exception is with a signed integer. e.g. An 8-bit signed integer with a value of -128 looks like:
10000000
So after checking that the number is greater than zero, we can use a clever little bit hack to test that one and only one bit is set.
bool is_power_of_2(int x) {
return x > 0 && !(x & (x−1));
}
For more bit twiddling see here.
Approach #1:
Divide number by 2 reclusively to check it.
Time complexity : O(log2n).
Approach #2:
Bitwise AND the number with its just previous number should be equal to ZERO.
Example: Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 0 0 0 0 = 0.
Time complexity : O(1).
Approach #3:
Bitwise XOR the number with its just previous number should be sum of both numbers.
Example: Number = 8 Binary of 8: 1 0 0 0 Binary of 7: 0 1 1 1 and the bitwise XOR of both the numbers is 1 1 1 1 = 15.
Time complexity : O(1).
http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html