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?