Power of Two

franklinqin0 MathBit

# Solution

# Vanilla Iteration

Could also do in recursion instead of while loop but omitted.

We could either increase or decrease w/ $O(\log n)$ time and constant space.

# Increase

We could increase acc till it's equal to or larger than n.

def isPowerOfTwo(self, n: int) -> bool:
    if n < 1:
        return False
    elif n == 1:
        return True
    acc = 1
    while acc < n:
        acc *= 2
        if acc == n:
            return True
    return False

1
2
3
4
5
6
7
8
9
10
11

# Decrease

We could decrease n till it's equal to or smaller than 1.

def isPowerOfTwo(self, n: int) -> bool:
    if n < 1:
        return False
    while n > 1:
        n /= 2
    return n == 1

1
2
3
4
5
6

# Bit Manipulation

Both solutions take constant time and constant space.

# Two's Complement

In two's complement notation, -n = ~n + 1. This - operation on n would revert all bits except the rightmost 1-bit. Now n & (-n) would just keep that rightmost 1-bit. If n is a power of 2, it has just one 1-bit and n & (-n) == n would return 0.

def isPowerOfTwo(self, n: int) -> bool:
    if n == 0:
        return False
    return n & (-n) == n

1
2
3
4

# Get Rid of Rightmost 1-bit

If n is a power of 2, it has just one 1-bit. If subtract n by 1, all the lower bits would become 1's and n & (n-1) == 0.

def isPowerOfTwo(self, n: int) -> bool:
    if n == 0:
        return False
    return n & (n-1) == 0

1
2
3
4

Power of Three x to the n