Problem

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 == 2x.

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?

Analysis

1. If n is a power of two:

n = 2i (`i ≥ 0`)
  ≥ 20 = 1

=> If n < 0, n is not a power of two.

2. If n is a power of two:

The binary form of every 2i (i is a non-negative number):

2010 = 110 = 12

2110 = 210 = 102

2210 = 410 = 1002

2310 = 810 = 10002

...

2i10 = 100...002 (only one 1-digit at the first position and followed by total `i` 0-digit numbers)
       |__i__|

2.1. If i = 0:

n = 20 = 1 > 0
n & (n-1) = 1 & 0 = 0

2.2. If i > 0:

The binary form of every 2i - 1:

2110 - 1 = 110 = 012

2210 - 1 = 310 = 0112

2310 - 1 = 710 = 01112

...

2i10 - 1 = 011...112 (total `i` 1-digit numbers)
           |__i__|

For i > 0, we have:

n - 1 = 2i10 - 1 ≥ 0
n & (n-1) = 2i10 & 2i10 - 1 = 100...002 & 011...112 = 0
                             |___i___|   |__i__|

If n is a power of two: n & (n-1) = 0.

3. If n is not an power of two, we have:

             n10 = [0....0][1....1][0....0]2 (i ≥ 0, j ≥ 2, k ≥ 1)
                   |__i__| |__j__| |__k__|

         (n-1)10 = [0....0][1....1]0[1....1]2
                   |__i__| |_j-1_|  |__k__|

x = n10 & (n-1)10 = [0....0][1.....][0....0]2
                   |__i__| |_j-1_| |_k+1_|

• j ≥ 2 => j-1 ≥ 1. So x has at least one 1-digit number => x > 0.

If n is not a power of two: n & (n-1) > 0.

As result, n is a power of two if and only if n > 0 and n & (n-1) = 0.

Approaches

Approach 1

Approach

• n is a power of two if and only if n > 0 and n & (n-1) = 0.

Solutions

func isPowerOfTwo(n int) bool {
	return n > 0 && n&(n-1) == 0
}

Complexity

• Time Complexity: O(1).