Is Power of 2 (Brian Kernigan Algo)

231.Power of Two

Bit Manipulation

Math

Problem Statement:

Given an integer n, return true if it is a power of two. An integer n is a power of two, if there exists an integer x such that n == 2^x.

Example:

Input:

n = 16

→

Output:

true

Java Solution:

// Brian Kernighan algorithm, one bit set
public boolean isPowerOfTwo(int n) {
    if (n == 0) return false;
    return (n & (n - 1)) == 0;  // Check if only one bit is set
}

Python Solution:

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

C++ Solution:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0) return false;
        return (n & (n - 1)) == 0;
    }
};

Explanation:

Brian Kernighan's algorithm uses the fact that powers of 2 have exactly one bit set in their binary representation. By using n & (n-1), we remove the rightmost set bit. If the result is 0, n had only one bit set, meaning it's a power of 2.

Complexity:

Time: O(1) | Space: O(1)