Power of Two

Q: How do you check if a number is a power of two?

Return true when n > 0 and n & (n-1) equals 0. A power of two has exactly one 1 bit, and n & (n-1) clears it. Without bit operations, halve n while it is even and check that you end at 1.

Q: What is the time complexity of Power of Two?

The n & (n-1) check runs in O(1) time and space. The halving loop runs in O(log n) time, at most 31 steps for a 32-bit integer.

Q: Is 1 a power of two? Is 0?

1 is a power of two, because 2^0 = 1 . 0 is not: no whole exponent gives 0, and it has no 1 bit at all. Negative numbers are never powers of two either.

EasyBit manipulation

+10

You get an integer n. Return true if n is a power of two, meaning n = 2^k for some whole number k ≥ 0, and false otherwise. So 1, 2, 4 and 8 count, while 0, 6 and every negative number do not.

Function

isPowerOfTwo(n: integer) → boolean

ninteger: the integer to test, which may be zero or negative
Returnsboolean: true if n equals 2^k for some k ≥ 0, false otherwise

Constraints

-2³¹ ≤ n ≤ 2³¹-1

Examples

Input: n = 16
Output: true
Explanation: 16 = 2 × 2 × 2 × 2 = 2^4. In binary it is 10000, a single 1 bit.

Input: n = 24
Output: false
Explanation: 24 = 8 × 3. Halving gives 12, 6 and then 3, which is odd but not 1. In binary 24 is 11000, two 1 bits.

Input: n = 1
Output: true
Explanation: 1 = 2^0, so it is a power of two. Its binary form 1 has exactly one 1 bit.

Follow-up

With the same bit tricks, can you test whether n is a power of four without a loop?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

In binary, a power of two is one 1 bit followed by zeros, like 10000 for 16. You can confirm that shape by halving n until it turns odd, or in one step with n & (n-1), which clears the lowest 1 bit and leaves 0 only when it was the only one. Check zero and negatives first.

Divide by 2 while the number is even

Intuition

Dividing 2^k by 2 exactly k times lands on 1, and every value on the way is even. A number with an odd factor above 1 stops halving at an odd number that is not 1.

Return false for n ≤ 0 before the loop. No power of two is zero or negative, and 0 is even and halves to 0, so the loop would never end. Each step halves n, so a 32-bit input takes at most 31 steps.

Algorithm

If n ≤ 0, return false.
While n is even, divide it by 2.
Return whether n is now 1.

def isPowerOfTwo(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Clear the lowest set bit with n & (n-1)

Intuition

Subtracting 1 turns the lowest 1 bit into 0 and every 0 below it into 1, and leaves the higher bits alone. A power of two has no higher bits: 16 is 10000, 15 is 01111, and 16 & 15 is 0. Any other positive number has a higher 1 bit that appears in both numbers, so the AND is not 0. For 24 you get 11000 & 10111, which is 10000.

Check n > 0 first. 0 & -1 is 0, and in 32-bit arithmetic -2^31 is a lone 1 bit followed by 31 zeros, so the AND alone would accept both. The whole test is one comparison, one subtraction and one AND.

Algorithm

If n ≤ 0, return false.
Compute n & (n-1), which is n with its lowest 1 bit cleared.
Return whether that result is 0.

def isPowerOfTwo(n):
    # One set bit: n - 1 flips it and every bit below, so the AND is 0.
    return n > 0 and n & (n - 1) == 0

Pitfalls and edge cases

Skipping the sign check. 0 passes the AND test, and with 32-bit integers so does -2^31, a single 1 bit. Both must return false.
Running the halving loop on 0. Zero is even and halves to 0, so the loop never ends.
Dropping the parentheses. == binds tighter than &, so in C, C++ and JavaScript n & n - 1 == 0 means n & ((n - 1) == 0) and gives wrong answers without an error. Write (n & (n - 1)) == 0.
Using logarithms. In double precision log(536870912) / log(2) is 29.000000000000004, so a whole-number check calls 2^29 false.

Frequently asked questions3

How do you check if a number is a power of two?

Return true when n > 0 and n & (n-1) equals 0. A power of two has exactly one 1 bit, and n & (n-1) clears it. Without bit operations, halve n while it is even and check that you end at 1.

What is the time complexity of Power of Two?

The n & (n-1) check runs in O(1) time and space. The halving loop runs in O(log n) time, at most 31 steps for a 32-bit integer.

Is 1 a power of two? Is 0?

1 is a power of two, because 2^0 = 1. 0 is not: no whole exponent gives 0, and it has no 1 bit at all. Negative numbers are never powers of two either.

def isPowerOfTwo(n):
    # Write code here

Test #1

Test #2

Test #3

Argument

n = 16

Expected Output

true