222. Check if a Number Is a Power of 2

Given an integer n, print 'Yes' if it is a power of 2 (1, 2, 4, 8, ...), otherwise print 'No'. 0 is not a power of 2.

Input: A single line contains the integer n. Output: Print "Yes" if n is a power of 2, otherwise print "No".

0 <= n <= 10^9

Don't forget the n != 0 special case - 0 has no set bits at all, so n & (n-1) trivially equals 0 for n=0 too, even though 0 is explicitly NOT a power of 2 per this problem's own statement.

Powers of 2 (1, 2, 4, 8, 16...) have a very distinctive binary pattern: exactly ONE bit is turned on, and it's always a single 1 followed by zeros. Check whether a given number has that exact pattern. Brute force: Repeatedly divide n by 2 as long as it's even, and check if you eventually reach exactly 1 - this works, but takes a full loop when a single bitwise check answers the same question instantly. Optimised: A power of 2 is defined by having exactly one set bit. The n & (n-1) trick clears the lowest set bit - if that single clear leaves NOTHING (result is 0), there was only ever one bit to clear, meaning n was a power of 2 all along.

For any positive power of 2, the binary representation is a single 1 followed by zeros (e.g. 1000), and subtracting 1 flips that bit and all bits below it to give a number with no bits in common with the original (0111). So n & (n - 1) equals 0 if and only if n has at most one set bit. Checking n > 0 && (n & (n - 1)) == 0 answers the question in a single constant-time bitwise AND and comparison, with no loop at all - the fastest possible check. Time: O(1) Space: O(1)

Instead of dividing, count the number of 1-bits in n's binary representation by repeatedly checking the last bit (n & 1) and right-shifting n until it becomes 0. A power of 2 is exactly a number whose binary representation has a single 1-bit, so if the final popcount equals 1 (and n > 0), it is a power of 2. This avoids division entirely in favor of cheaper bitwise operations, though it still takes one iteration per bit. Time: O(log n) Space: O(1)

Handle 0 as a special case (not a power of 2), then repeatedly divide n by 2 as long as it divides evenly (remainder 0), counting how many times this succeeds. If you eventually reach exactly 1, n was a power of 2; if you hit a point where the number is odd but not 1, it isn't. This directly simulates the definition of 'power of 2' by repeated halving and is easy to reason about, taking one division per bit of n. Time: O(log n) Space: O(1)

1. Recall the n & (n-1) trick from the previous lesson, which clears the lowest set bit. 2. If n has EXACTLY one set bit (a power of 2), clearing that one bit leaves exactly 0. 3. If n has more than one set bit, clearing the lowest one still leaves at least one other bit set (a nonzero result). 4. So: n is a power of 2 if and only if (n & (n-1)) equals 0 - with the special case that n itself must not be 0, since 0 trivially satisfies the formula but isn't actually a power of 2.

Time: O(1) - a single subtraction and a single AND operation, regardless of n's size. Space: O(1) - no extra storage needed.

Test n = 0 (must print "No" despite n & (n-1) also being 0), n = 1 (2^0, "Yes"), and a non-power-of-2 value near the upper bound 10^9.

This is one of the most commonly asked 'one-liner bit trick' interview questions - be ready to write `n != 0 and (n & (n - 1)) == 0` from memory, including the important n != 0 special case.