Problem (short)

Given an integer n, return true if it is a power of two. Otherwise return false.
(Edge: n <= 0 → false.)

Best approach (DSA reasoning + proof) — Bit trick (recommended)

Idea (insight): A power of two in binary has exactly one 1 bit (e.g. 1=1, 2=10, 4=100, …). If you do n & (n-1) you clear the lowest set bit. For a number with a single 1 bit, that result becomes 0.

Step-by-step algorithm

1. If n <= 0 return false.
2. Compute m = n & (n - 1).
3. If m == 0 → true else false.

Correctness: subtracting 1 flips all bits after the lowest 1 (including it). ANDing clears that 1 — only zero when there was exactly one 1.

Complexity: Time O(1) (constant-time bit ops on fixed-size ints). Space O(1).

PHP implementation (recommended):

<?php
declare(strict_types=1);

function isPowerOfTwoBit(int $n): bool {
    if ($n <= 0) {
        return false;
    }
    // clear lowest set bit; if result is 0 => only one bit was set
    return (($n & ($n - 1)) === 0);
}

// Quick test
$tests = [1, 2, 3, 4, 16, 218, 0, -2];
foreach ($tests as $t) {
    echo "n={$t} => " . (isPowerOfTwoBit($t) ? "true" : "false") . PHP_EOL;
}

Other valid approaches (with DSA notes)

Approach 2 — Repeated divide by 2

Idea: Keep dividing by 2 while n % 2 == 0. If you end at 1, it’s power of two.

Steps:

1. If n <= 0 return false.
2. While n % 2 == 0, set n = n / 2 (use integer division).
3. Return n == 1.

Complexity: O(log n) time (number of divisions ~ exponent), O(1) space.

PHP code:

function isPowerOfTwoDiv(int $n): bool {
    if ($n <= 0) return false;
    while ($n % 2 === 0) {
        $n >>= 1; // bit-shift same as integer divide by 2
    }
    return $n === 1;
}

Approach 3 — Count ones in binary string

Idea: Convert to binary string and count '1' characters; exactly one => power of two.

Complexity: O(log n) time and O(log n) extra space.

PHP code:

function isPowerOfTwoString(int $n): bool {
    if ($n <= 0) return false;
    return substr_count(decbin($n), '1') === 1;
}

Approach 4 — Using logs (not recommended for exactness)

Idea: Check if log2(n) is an integer. But floating-point rounding can produce false negatives/positives, so this is fragile for large numbers.

PHP sketch (with caution):

function isPowerOfTwoLog(int $n): bool {
    if ($n <= 0) return false;
    $log2 = log($n, 2);
    $p = (int) round($log2);
    // verify by shifting (safer than comparing floats directly)
    return ($p >= 0) && ((1 << $p) === $n);
}

Note: Use this only if you understand floating precision issues and bounds in PHP.

Summary / Recommendation

• Use bit trick n > 0 && (n & (n-1)) == 0 — it’s elegant, constant-time, and standard in DSA interviews.
• If interviewer expects loop-based solution, use the divide-by-2 method and explain its O(log n) complexity.
• Avoid pure log-based checks in production/interview unless you add robust verification because of floating-point imprecision.