Power of Two

Bit Manipulation

EasyLeetCode #231

5 min

Problem Statement

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

Examples

Example 1:

Input: n = 1

Output: true

Explanation: 2^0 = 1

Example 2:

Input: n = 16

Output: true

Explanation: 2^4 = 16

Example 3:

Input: n = 3

Output: false

Solution (Bitwise Trick)

A number is a power of two if and only if it has exactly one bit set to 1 in its binary representation. For example, 8 is 1000 and 16 is 10000.

A clever trick to check this is using the expression n & (n - 1). If n is a power of two, n - 1 will have all the bits after the single set bit as 1s. The AND operation will then result in 0.

Algorithm Steps

First, check if n is greater than 0. Powers of two must be positive.
Calculate n & (n - 1).
If the result is 0, then n is a power of two.

Enter a number:

00010000

(16)

n - 1

00001111

(15)

Result

00000000

(0)

Is it a power of two?

Yes

Condition: n > 0 and (n & (n - 1)) === 0

Power of Two Solution


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