Program to find whether a no is power of two

The problem, simply

You get a whole number n. Say true if n is a power of two, meaning n is 1, 2, 4, 8, 16, 32 and so on, each one double the last. Otherwise say false.

0 and negative numbers are never powers of two.

A story to remember it

Picture it

Examples

Way 1: the simple way

Fold the strip. While n is even, cut it in half. If you end at 1, it was a power of two.

1. If n is 0 or less, say false.
2. While n is even, set n = n / 2.
3. Say true only if n is now 1.

class Solution {
    public static boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) {
            n /= 2;            // fold in half
        }
        return n == 1;         // only a power of two folds all the way down to 1
    }
}

How long it takes: one fold per halving, up to 30 for an int, O(log n). Extra room: O(1).

Way 2: the clever way

A power of two has exactly one 1 in bits. The trick n & (n - 1) wipes out the lowest 1 of n. If nothing is left after that, there was only one 1.

Why it wipes out the lowest 1: taking 1 away turns the lowest 1 into a 0 and every 0 below it into a 1. Above that spot nothing changes. So n and n - 1 are opposite from the lowest 1 down, and AND makes that whole part 0.

1. Say false if n is 0 or less.
2. Say true if (n & (n - 1)) == 0.

class Solution {
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;   // positive, and only one 1
    }
}

How long it takes: one subtraction, one AND, one compare, O(1). Extra room: O(1).

Watch out for

• Brackets matter. In Java == is done before &, so n & n - 1 == 0 does not even compile. Write (n & (n - 1)) == 0.
• Using Math.log(n) / Math.log(2) and checking for a whole number. Floating point error makes this fail for some large inputs.
• n % 2 == 0 in Way 1 is fine because n is positive there. For negative numbers % can give -1.

What interviewers ask next

• Another one line check? n > 0 && (n & -n) == n. n & -n keeps only the lowest 1, so it equals n only when that is the only 1.
• Power of four? It must be a power of two, and its single 1 must sit on an even spot: n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0.
• Power of three? Bits do not help. The biggest power of three in an int is 1162261467, so n > 0 && 1162261467 % n == 0.
• Smallest power of two that is at least n? Copy the top 1 into every bit below with x |= x >> 1, >> 2, >> 4, >> 8, >> 16 on x = n - 1, then add 1.

Remember this

Grown-up words: folding in half is dividing by 2, the lit bulbs are set bits, and wiping out the lowest 1 with n & (n - 1) is Brian Kernighan's trick.