Problem

Given an integer n, return true if it is a power of two.

Example

Input:  16
Output: true

Input:  3
Output: false

Solution

A power of two has exactly one bit set. n & (n-1) clears the lowest set bit. If result is 0, n was a power of two.

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

function isPowerOfTwo(n) {
    return n > 0 && (n & (n - 1)) === 0;
}

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

public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Complexity

• Time: O(1)
• Space: O(1)

Explanation

Powers of 2 in binary look like 1, 10, 100, 1000… Subtracting 1 gives 0, 1, 11, 111… AND-ing them always gives 0.