LeetCode 231: Power of Two

🪜 Step 1: My Initial Solution – Converting to Binary

My first thought was:
A number is a power of two only if its binary representation contains exactly one ‘1’.
So I wrote a function to convert a number to its binary form and then counted how many 1s it had.

class Solution {
public:
    string set_bit(int num){
        if (num == 0) return "0";
        string bin = "";
        while (num > 0){
            int rem = num % 2;
            bin += to_string(rem);
            num = num / 2;
        }
        return bin;  // binary in reverse order
    }

    bool isPowerOfTwo(int n) {
        string bits = set_bit(n);
        int count = 0;
        for (int i = 0; i < bits.length(); i++){
            if (bits[i] == '1') count++;
        }
        return count == 1;
    }
};

It worked! Even though the binary string is reversed, it didn’t matter since I only cared about the number of 1s.
✅ What I Learned:

1. How to convert a number to binary using %
2. How to analyze the number of set bits (1s).

🧠 Step 2: A Cleaner Way – Count Set Bits Without Strings

While reviewing other solutions, I realized I didn’t need to build a binary string at all. I could count the set bits directly while dividing the number.

Here’s the improved solution:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        int count = 0;

        while (n > 0) {
            if (n % 2 == 1) count++;  // count set bits
            n /= 2;
        }

        return count == 1;
    }
};

Much better! This avoids unnecessary string manipulation and directly counts the 1s.

💥 Step 3: The Most Efficient Way – Bit Manipulation Trick

Finally, I stumbled upon this line of genius:

return n > 0 && (n & (n - 1)) == 0;

This is the most optimized and elegant solution to check if a number is a power of two. But… how does it work?
🔍 How n & (n - 1) == 0 Works
Example 1:
n = 8 → binary = 1000
n - 1 = 7 → binary = 0111
so (8&7)==0 is true,
and 8>0 is also true ie n > 0 && (n & (n - 1)) gives 1. ✅ result is 1 → so 8 is a power of 2

Example 2:
n = 6 → binary = 1100
n - 1 = 5 → binary = 1010
so (6&5)==0 is false,
and 6>0 is true ie n > 0 && (n & (n - 1)) gives 0. ✅ result is 0 → so 6 is not a power of 2
🧠 Why This Works:
A power of two has exactly one set bit. Subtracting 1 from it flips that bit and all bits to the right of it.
So n & (n - 1) results in 0 only if n had just one set bit.

Here’s the final optimized version:

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