Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to check if a given number is a power of two?

Tags:

python

The code below isn't working right for some inputs.

a, i = set(), 1
while i <= 10000:
    a.add(i)
    i <<= 1

N = int(input())
if N in a:
    print("True")
else:
    print("False")

My initial idea was to check for each input if it's a power of 2 by starting from 1 and multiplying by 2 until exceeding the input number, comparing at each step. Instead, I store all the powers of 2 in a set beforehand, in order to check a given input in O(1). How can this be improved?

like image 348
krishna5001 Avatar asked Jul 14 '19 08:07

krishna5001


People also ask

How do you check if a large number is a power of 2?

The idea is to repeatedly divide the large number (represented as a string) by 2. To perform division, we traverse digits from right to left. If the last digit itself is not divisible by 2, we return 0. Otherwise, we follow the school method of division.

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

Following are detailed step. 1) Initialize pow = x, i = 1 2) while (pow < y) { pow = pow*pow i *= 2 } 3) If pow == y return true; 4) Else construct an array of powers from x^i to x^(i/2) 5) Binary Search for y in array constructed in step 4. If not found, return false. Else return true.

How do you check if a number is a power of 2 using bit?

If (x & (x-1)) is zero then the number is power of 2. For example, let x be 8 ( 1000 in binary); then x-1 = 7 ( 0111 ). This outputs the bit is power of 2 . This outputs the bit is not power of 2 .


4 Answers

Bit Manipulations

One approach would be to use bit manipulations:

(n & (n-1) == 0) and n != 0

Explanation: every power of 2 has exactly 1 bit set to 1 (the bit in that number's log base-2 index). So when subtracting 1 from it, that bit flips to 0 and all preceding bits flip to 1. That makes these 2 numbers the inverse of each other so when AND-ing them, we will get 0 as the result.

For example:

                    n = 8

decimal |   8 = 2**3   |  8 - 1 = 7   |   8 & 7 = 0
        |          ^   |              |
binary  |   1 0 0 0    |   0 1 1 1    |    1 0 0 0
        |   ^          |              |  & 0 1 1 1
index   |   3 2 1 0    |              |    -------
                                           0 0 0 0
-----------------------------------------------------
                    n = 5

decimal | 5 = 2**2 + 1 |  5 - 1 = 4   |   5 & 4 = 4
        |              |              |
binary  |    1 0 1     |    1 0 0     |    1 0 1
        |              |              |  & 1 0 0
index   |    2 1 0     |              |    ------
                                           1 0 0

So, in conclusion, whenever we subtract one from a number, AND the result with the number itself, and that becomes 0 - that number is a power of 2!

Of course, AND-ing anything with 0 will give 0, so we add the check for n != 0.


math functions

You could always use math functions, but notice that using them without care could cause incorrect results:

  • math.log(x[, base]) with base=2:

    import math
    
    math.log(n, 2).is_integer()
    
  • math.log2(x):

    math.log2(n).is_integer()
    

Worth noting that for any n <= 0, both functions will throw a ValueError as it is mathematically undefined (and therefore shouldn't present a logical problem).

  • math.frexp(x):
    abs(math.frexp(n)[0]) == 0.5
    

As noted above, for some numbers these functions are not accurate and actually give FALSE RESULTS:

  • math.log(2**29, 2).is_integer() will give False
  • math.log2(2**49-1).is_integer() will give True
  • math.frexp(2**53+1)[0] == 0.5 will give True!!

This is because math functions use floats, and those have an inherent accuracy problem.


(Expanded) Timing

Some time has passed since this question was asked and some new answers came up with the years. I decided to expand the timing to include all of them.

According to the math docs, the log with a given base, actually calculates log(x)/log(base) which is obviously slow. log2 is said to be more accurate, and probably more efficient. Bit manipulations are simple operations, not calling any functions.

So the results are:

Ev: 0.28 sec

log with base=2: 0.26 sec

count_1: 0.21 sec

check_1: 0.2 sec

frexp: 0.19 sec

log2: 0.1 sec

bit ops: 0.08 sec

The code I used for these measures can be recreated in this REPL (forked from this one).

like image 52
Tomerikoo Avatar answered Oct 13 '22 11:10

Tomerikoo


Refer to the excellent and detailed answer to "How to check if a number is a power of 2" — for C#. The equivalent Python implementation, also using the "bitwise and" operator &, is this:

def is_power_of_two(n):
    return (n != 0) and (n & (n-1) == 0)

As Python has arbitrary-precision integers, this works for any integer n as long as it fits into memory.

To summarize briefly the answer cited above: The first term, before the logical and operator, simply checks if n isn't 0 — and hence not a power of 2. The second term checks if it's a power of 2 by making sure that all bits after that bitwise & operation are 0. The bitwise operation is designed to be only True for powers of 2 — with one exception: if n (and thus all of its bits) were 0 to begin with.

To add to this: As the logical and "short-circuits" the evaluation of the two terms, it would be more efficient to reverse their order if, in a particular use case, it is less likely that a given n be 0 than it being a power of 2.

like image 37
john-hen Avatar answered Oct 13 '22 10:10

john-hen


In binary representation, a power of 2 is a 1 (one) followed by zeros. So if the binary representation of the number has a single 1, then it's a power of 2. No need here to check num != 0:

print(1 == bin(num).count("1")) 
like image 8
Yehuda Katz Avatar answered Oct 13 '22 11:10

Yehuda Katz


The bin builtin returns a string "0b1[01]?" (regex notation) for every strictly positive integer (if system memory suffices, that is), so that we can write the Boolean expression

'1' not in bin(abs(n))[3:]

that yields True for n that equals 0, 1 and 2**k.

1 is 2**0 so it is unquestionably a power of two, but 0 is not, unless you take into account the limit of x=2**k for k → -∞. Under the second assumption we can write simply

check0 = lambda n: '1' not in bin(abs(n))[3:]

and under the first one (excluding 0)

check1 = lambda n: '1' not in bin(abs(n))[3:] and n != 0

Of course the solution here proposed is just one of the many possible ones that
you can use to check if a number is a power of two... and for sure not the most
efficient one but I'm posting it in the sake of completeness :-)

like image 2
gboffi Avatar answered Oct 13 '22 10:10

gboffi