Given a number, you need to check if the number is a power of 2, return true or false accordingly.
Example:
Input: 1
Output: True
Because 2^0 is 1Input: 15
Output: False
Because 15 is not a power of 2.Input: 8
Output: True
Because 2^3 is 8
We can solve this by 2 methods:
1. Iterative method
2. Bitwise Operation
1. Iterative method.
In the iterative method, we divide the number by 2 repeatedly and check the modulo of the number. If the mod value is equal to 0, then we return true, if the mod value is not ‘0’, then we return false.
2. Bitwise operation
We can solve it by bitwise operation.
In bitwise operation, we perform a bitwise “&” of the current number and it’s previous number. If the value is equal to “0” then we return true else false.
i.e
n & (n -1) == 0
Now why do we do it?
Let’s take an example and understand it.
We shall take
n = 2 n-1 = 1
n = 4 n-1 = 3
n = 8 n-1 = 7
n = 9 n-1 = 8
n = 2 binary = 0 0 1 0
n = 1 binary = 0 0 0 1
------------------------------
0 0 0 0
n = 4 binary = 0 1 0 0
n = 3 binary = 0 0 1 1
------------------------------
0 0 0 0
n = 8 binary = 1 0 0 0
n = 7 binary = 0 1 1 1
----------------------------------
0 0 0 0
n = 9 binary = 1 0 0 1
n = 8 binary = 1 0 0 0
-----------------------------
1 0 0 0
As you can see above, if n&(n-1) == 0 then it it is a power of 2.
Solution in C++
#include<iostream>
using namespace std;
bool iterative_method(int n)
{
while(n > 1)
{
if(n % 2 != 0)
{
return false;
}
n /= 2;
}
return n == 1;
}
bool bitwise_operation(int n)
{
return n > 0 && (n & n - 1) == 0;
}
int main()
{
int num = 16;
if(iterative_method(num))
{
cout<<num << " is power of 2, iterative method"<<endl;
}
else
{
cout<<num << " is NOT power of 2, iterative method"<<endl;
}
if(bitwise_operation(num))
{
cout<<num << " is power of 2, bitwise method"<<endl;
}
else
{
cout<<num << " is NOT power of 2, bitwise method"<<endl;
}
return 0;
}