How to check if a number is a power of two. Give an integer, write a function to check if it is a power of two.
Example –
Input – 16 – 16 is a power of 2 (2^4).
Input – 15 – 15 is not a power of 2.
Input – 32- 32 is a power of 2 (2^5).
We can use multiple approaches to check whether a number is a power of 2 or not.
How to Check if a Number is a Power of 2
Method 1 : Check whether a number is perfectly divisible by 2.
In this approach, We’ll check whether a number is perfectly divisible by 2. If a number is perfectly divisible by 2 then it’s remainder is 0.
We’ll repeat this step until n becomes 1. In each step, we check if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public boolean isPowerOfTwo(int n) { /* * If number is less than or equal to * zero then return false. */ if (n <= 0) return false; while (n % 2 == 0) n = n/2; return n == 1; } |
Let’s consider the binary representation of any number that is a power of 2. We’ll find only one bit is set in their binary representation.
|
1 2 3 4 |
2 = 00000010 4 = 00000100 8 = 00001000 16 = 00010000 |
And number which is one less has following binary representation
|
1 2 |
3 = 00000011 7 = 00000111 |
If we do the bitwise AND of a number which is a power of 2 and a number which is one less than the number (one less than the number which is a power of 2) the result will be 0.
|
1 2 3 4 |
0 0 0 0 0 1 0 0 (Binary representation of 4) & 0 0 0 0 0 0 1 1 (Binary representation of 3) ------------------- 0 0 0 0 0 0 0 0 |
Power of 2 | Bit Manipulation – Java Code
|
1 2 3 4 5 |
//Power of two using bit manipuation public boolean isPowerOfTwoUsingBitManipulation(int n) { return n > 0 && ((n & (n-1)) == 0); } |
