How to Check If a Number Is a Power of Two

How can you tell if a number is a power of two?

That’s easy if it’s in the form 2ⁿ, where n is an integer. For example, 2¹², 2⁰, and 2^-37 are powers of two. That is by definition. But what about arbitrary positive numbers like 16,392, 524,288, or 0.00390625? Are they powers of two? Here’s how to tell — if they can be simplified to the form 2ⁿ, they are; if they can’t, they’re not.

We’ll go through this in two steps. First, we’ll see how to transform known powers of two, using simple arithmetic, into the form 2ⁿ. Then, we’ll see how to test whether an arbitrary number is a power of two.

(If you’re looking for information about how to tell if a number in a computer is a power of two, see my articles “What Powers of Two Look Like Inside a Computer” and “Ten Ways to Check if an Integer Is a Power Of Two in C”.)

Transforming a Power of Two Into the Form 2ⁿ

Some numbers you’ll recognize immediately as powers of two, despite not being expressed in the form 2ⁿ. For example: 2, 4, 8, 16, 1/2, 1/4, 1/8, 0.5, and 0.25. If you’re computer savvy, you’ll recognize other powers of two, like 256, 1,024, 4,096, and even 65,536. But what about powers of two you have not memorized?

In general, to show that a number is a power of two, you’ll need a procedure — that is, an algorithm — to put it into the form 2ⁿ. The algorithm to use depends on whether you are working with a positive or negative power of two (you don’t need an algorithm to tell you that 1, which is 2⁰, is a power of two).

Transforming Positive Powers of Two

The most straightforward way to convert a positive power of two into the form 2ⁿ is to count the number n of divisions by 2 that it takes to reach a quotient of 1. For example, the number 524,288 requires 19 divisions to reach 1, giving 2¹⁹:

1. 524,288/2 = 262,144
2. 262,144/2 = 131,072
3. 131,072/2 = 65,536
4. 65,536/2 = 32,768
5. 32,768/2 = 16,384
6. 16,384/2 = 8,192
7. 8,192/2 = 4,096
8. 4,096/2 = 2,048
9. 2,048/2 = 1,024
10. 1,024/2 = 512
11. 512/2 = 256
12. 256/2 = 128
13. 128/2 = 64
14. 64/2 = 32
15. 32/2 = 16
16. 16/2 = 8
17. 8/2 = 4
18. 4/2 = 2
19. 2/2 = 1

This example exposes a property common to all positive powers of two: all intermediate quotients are powers of two as well. In fact, the quotients form a descending sequence of consecutive nonnegative powers of two. For the number 524,288, the sequence of quotients is 2¹⁸, 2¹⁷, 2¹⁶, … , 2¹, 2⁰.

Transforming Negative Powers of Two

To convert a negative power of two into the form 2ⁿ, count the number n of multiplications by 2 that it takes to reach a product of 1 — then negate n. For example, the number 0.00390625 requires 8 multiplications to reach 1, giving 2^-8:

1. 0.00390625*2 = 0.0078125
2. 0.0078125*2 = 0.015625
3. 0.015625*2 = 0.03125
4. 0.03125*2 = 0.0625
5. 0.0625*2 = 0.125
6. 0.125*2 = 0.25
7. 0.25*2 = 0.5
8. 0.5*2 = 1.0

This example exposes a few properties common to all negative powers of two. First, notice that all intermediate products are powers of two. In fact, the products form an ascending sequence of consecutive nonpositive powers of two. For the number 0.00390625, the sequence of products is 2^-7, 2^-6, 2^-5, … , 2^-1, 2⁰. Also, all the products, except the last, end with the digit 5; all negative powers of two in decimal form end in 5!

This algorithm works just as well for negative powers of two expressed as fractions. For example, 1/128 is 2^-7:

1. 1/128*2 = 1/64
2. 1/64*2 = 1/32
3. 1/32*2 = 1/16
4. 1/16*2 = 1/8
5. 1/8*2 = 1/4
6. 1/4*2 = 1/2
7. 1/2*2 = 1

You don’t need to work with fractions; you could do one of the following instead:

1. Treat the denominator as a positive power of two, transform it using the division algorithm, and then negate the exponent
2. Convert the fraction to a decimal and transform it using the multiplication algorithm

Checking If an Arbitrary Number Is a Power Of Two

To this point we’ve demonstrated our algorithms on numbers that are known to be powers of two. But what if you don’t know that a number is a power of two to start with? The same algorithms will tell you.

Checking Positive Integers

For an integer greater than 1, which makes it a candidate for a positive power of two, use the “repeated division by 2” algorithm.

A number that is not a power of two will have quotients — in fact all of them — that are not powers of two. So, if you recognize a quotient not to be a power of two, you can stop; the original number is not a power of two. Of course, that only helps if you can recognize powers of two, which you may not because you’re using this algorithm!

The foolproof way to stop checking is to look for a quotient, not counting 1, that is odd. This means the quotient, and thus the number itself, cannot be a power of two. For example, 16,392 is not a power of two because it returns an odd quotient after three divisions:

1. 16,392/2 = 8,196
2. 8,196/2 = 4,098
3. 4,098/2 = 2,049

Another example is the number 524,289, which is odd to start with, so it’s not a power of two.

Checking Positive Decimals

For a decimal value between 0 and 1, which makes it a candidate for a negative power of two, use the “repeated multiplication by 2” algorithm.

A number that is not a power of two will have products — actually, all of them — that are not powers of two. How does this help you? A negative power of two ends in ‘5’, so a number that does not can’t be a power of two (that’s not to say that a number that ends in 5 must be a power of two). If you spot a product with a last digit other than 5, the original number is not a power of two.

If you’re not comfortable with this shortcut, simply execute the algorithm to completion. This means computing products until the last one equals or exceeds 1. If the number is not a negative power of two, the last product will never be exactly 1.

Here are some examples:

Is 0.0390625 a power of two?

No, because it yields a product greater than 1:

1. 0.0390625*2 = 0.078125
2. 0.078125*2 = 0.15625
3. 0.15625*2 = 0.3125
4. 0.3125*2 = 0.625
5. 0.625*2 = 1.25

I chose that example carefully. Not only do all the products end in 5, but they look like powers of two (they would be powers of two if they were shifted one place to the right). If you weren’t fooled by this along the way, you could have stopped multiplying.

Is 0.0178125 a power of two?

No, because a product (the fifth one) does not end in 5:

1. 0.0178125*2 = 0.035625
2. 0.035625*2= 0.07125
3. 0.07125*2 = 0.1425
4. 0.1425*2 = 0.285
5. 0.285*2 = 0.57

Again, if you noticed a product that was not a power of two before this point, you could have stopped.

Is 0.00390626 a power of two?

No. It does not end in 5, period.

Checking Positive Fractions

For a fraction in lowest terms and of the form 1/d, which makes it a candidate for a negative power of two, you have several options:

1. Treat the denominator as a positive integer and test it using the division algorithm
2. Convert the fraction to a decimal and test it using the multiplication algorithm
3. Test the fraction directly using the multiplication algorithm

To use option 3, multiply the numerator by 2 and reduce the fraction at each step to form the product. You can stop checking upon any of these conditions, which means the original number is not a power of two:

• The product is not a unit fraction
• The product is a unit fraction but its denominator is odd
• The product is a unit fraction but you recognize its denominator not to be a power of two

If you make it all the way to 1, congratulations — the number is a power of two.

Here’s an example:

1. 1/48*2 = 1/24
2. 1/24*2 = 1/12
3. 1/12*2 = 1/6
4. 1/6*2 = 1/3

1/48 is not a power of two because the denominator of the fourth product is 3, which is odd. In any case, you probably knew at the outset that 48 is not a power of two.

Exercises

Determine which of following are powers of two, and give their form as 2ⁿ:

1. 4,294,967,296
2. 3,145,728
3. 0.0009765625
4. 0.046875
5. 131,072
6. 1/294,912

Answers

1. 2³²
2. Not a power of two (the quotient does not become odd until after the 20th division, so it may have taken you a while to determine this)
3. 2^-10
4. Not a power of two (the product does not become 1; after 4 multiplications it is 0.75, and after 5 multiplications it is 1.5)
5. 2¹⁷
6. Not a power of two (after 15 multiplications on the fraction, the denominator of the product is odd)