Program to find whether a no is power of two

Problem Statement

Given a non-negative integer n, determine if it is a power of two. A number is a power of two if it can be expressed as 2^k for some non-negative integer k.

Example:

Noob-Friendly Explanation

Powers of two are: 1, 2, 4, 8, 16, 32, 64, 128...

Look at them in binary:

See the pattern? Every power of two has exactly one 1-bit! All others are 0.

Now look at non-powers-of-two:

They have more than one 1-bit!

So to check if a number is a power of two, we just need to check: does it have exactly one set bit?

Approach 1: Brute Force (Keep Dividing by 2)

Intuition

A power of two is divisible by 2 repeatedly until we reach 1. So keep dividing by 2. If we ever get an odd number that isn't 1, it's not a power of two.

Algorithm

1. If n <= 0, return false
2. While n > 1:
   • If n is odd (n % 2 != 0), return false
   • Divide n by 2
3. Return true (n == 1)

class Solution {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;

        while (n > 1) {
            if (n % 2 != 0) {
                return false; // odd number that's not 1
            }
            n = n / 2;
        }

        return true; // reduced to 1
    }

    public static void main(String[] args) {
        System.out.println(isPowerOfTwo(16));  // true
        System.out.println(isPowerOfTwo(5));   // false
        System.out.println(isPowerOfTwo(1));   // true
        System.out.println(isPowerOfTwo(0));   // false
        System.out.println(isPowerOfTwo(64));  // true
    }
}

Complexity Analysis

• Time Complexity: O(log N) — We divide by 2 at each step, so log₂(N) iterations
• Space Complexity: O(1) — Only using one variable

Approach 2: Optimal (Bit Manipulation)

Intuition

A power of two has exactly one set bit. The trick n & (n - 1) removes the lowest set bit. If after removing it the number becomes 0, it had only one set bit → power of two!

Example: n = 8 (1000), n-1 = 7 (0111), n & (n-1) = 0000 → Power of two! Example: n = 6 (110), n-1 = 5 (101), n & (n-1) = 100 ≠ 0 → Not a power of two.

Algorithm

1. Check if n > 0 (0 and negatives are not powers of two)
2. Check if n & (n - 1) == 0
3. If both conditions met, return true

class Solution {
    public static boolean isPowerOfTwo(int n) {
        // n must be positive AND have only one set bit
        return n > 0 && (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        System.out.println(isPowerOfTwo(16));  // true
        System.out.println(isPowerOfTwo(5));   // false
        System.out.println(isPowerOfTwo(1));   // true
        System.out.println(isPowerOfTwo(0));   // false
        System.out.println(isPowerOfTwo(64));  // true
        System.out.println(isPowerOfTwo(128)); // true
        System.out.println(isPowerOfTwo(100)); // false
    }
}

Complexity Analysis

• Time Complexity: O(1) — Just one bitwise operation and a comparison
• Space Complexity: O(1) — No extra space

Key Takeaways

1. Powers of 2 in binary: Always have exactly one 1-bit (e.g., 1000, 10000)
2. n & (n-1) == 0: The classic one-liner to check power of two
3. Edge Case — Zero: 0 is NOT a power of two, so always check n > 0
4. Java Built-in: Integer.bitCount(n) == 1 also works, but the bit trick is faster