Leetcode: Power of Two
Given an integer n
, return true
if it is a power of two. Otherwise, return false
.
An integer n
is a power of two, if there exists an integer x
such that n == 2^x
.
Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16
Example 3:
Input: n = 3
Output: false
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
Solution
Loops/Recursion seems quite straight forward. We use a bitwise approach here. Let’s take a look at the some numbers that are the power of two and their binary representation.
Decimal | Binary |
---|---|
2 | 10 |
4 | 100 |
8 | 1000 |
16 | 10000 |
32 | 100000 |
For all numbers, the first bit are true
and all the remaining bits are false
. You can check the
binary representation based on that condition, but it’s still a loop on the binary string.
If we minus each number by 1, we get a new number with all bits are true
(all bits are inverted).
Decimal | Binary |
---|---|
2-1 | 1 |
4-1 | 11 |
8-1 | 111 |
16-1 | 1111 |
32-1 | 11111 |
If we use &
bitwise operator between n
and n-1
, the result will be 0
.
Decimal | Binary | Result |
---|---|---|
2 & 1 | 10 & 01 | 00 |
4 & 3 | 100 & 011 | 000 |
8 & 7 | 1000 & 0111 | 0000 |
16 & 15 | 10000 & 01111 | 00000 |
32 & 31 | 100000 & 011111 | 000000 |
Working code in C#
public class Solution {
public bool IsPowerOfTwo(int n)
{
return n > 0 && (n & (n - 1)) == 0;
}
}
Who the hell could think of this bitwise solution?