0

I need a simple way to find whether the variable originalnumber is a power of two. I'd rather avoid using functions, especially since I'm incredibly confused by parameters, so something like the division thing would be useful

This is in Python 3.

Something similar to how you find if a number is divisible by another number would be useful.

At first I had (just an example for what I'm looking for):

if originalnumber % 2 == 0:
     print("is power of 2")
else:
     print("is not power of 2")
kenlukas
  • 3,616
  • 9
  • 25
  • 36
imtired
  • 11
  • 3

4 Answers4

1

There's an easy way, but you'll need to use a math function:

import math
2 ** int(math.log(n, 2)) == n

Here we're checking if the number n is a power of two by using simple logarithmic identities.

To explain it in words: if 2 to the power of the base-2 logarithm of n, equals n, it's because n is a power of 2.

Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • What does the 2 ** do? – Corsaka Oct 07 '19 at 12:06
  • That's the power operator in Python: `x ** y` is `x` to the power of `y`. – Óscar López Oct 07 '19 at 12:06
  • doesn't work for 536870912 Problem with that approach is, that there can be rounding errors. as floating point numners are not precise – gelonida Oct 07 '19 at 12:15
  • 1
    @Óscar López Yes, this will work. there is one theoretic issue: If the calculated value would not be slightly to big (eg. 29.000000000000004) , but slightly to small (28.99999999999999999996) your int conversion would fail. To be absolutely paranoid you had too do `2 ** int(math.log(n, 2) + .5) == n` Though at least on my machine I did not find any value, that was too small, they were all too large (I tested with powers of 2 between 1 and 600) – gelonida Oct 07 '19 at 13:27
  • 1
    @ÓscarLópez Just for fun: The first number that would fail is 2 ** 13298, (where the calculated result is too small 13297.999999999998) – gelonida Oct 07 '19 at 13:57
1

You might convert the number to a binary string and verify that all but the first digit are "0"?

def is_power_of_two(n):
    return "{:b}".format(n)[1:].replace("0", "")  == ""

To understand exactly how this works you had to:

  • know the binary number system
  • read about how to declare and use functions.
  • read about string formatting()
  • read about string functions (replace())
gelonida
  • 5,327
  • 2
  • 23
  • 41
  • 1
    It almost works. It should be `"{:b}".format(n)[1:].replace("0", "") == ""` (`n` instead of `16` and `""` instead of `0`). Otherwise, I think it is the best answer. – ImranD Oct 07 '19 at 12:25
  • Thanks Imran. I overlooked that one – gelonida Oct 07 '19 at 13:19
0

You would do this through the math.log function, which is part of the math package.

import math
base = 2
number = 8
print(math.log(number,base))

Output: 3

You can then check if this output is an integer or a float, and go from there.

Corsaka
  • 364
  • 3
  • 15
  • 2
    doesn't work for 536870912 ? `math.log(536870912, 2)` results in `29.000000000000004` – gelonida Oct 07 '19 at 12:17
  • After some looking at this and thinking way harder than I probably needed to I now understand, thanks! – imtired Oct 07 '19 at 12:18
  • @gelonida such are the limitations of coding. Could be circumvented with a BigInt, but for most cases, 536.87 million would be enough. – Corsaka Oct 08 '19 at 08:16
  • It's not really a coding limitation. It is a known limitation of floating point operations to not yield exact results for certain operations. Look at @ÓscarLópez solution, which makes the code more robust. (and which can with a minor change be made even more robust) I believe code should be made as robust as possible if the cost is negligible. What's also a good idea is to comment known limitations of an implementation. So at least when reusing the code lateron you can decide whether this is an issue or not for the new use case. – gelonida Oct 08 '19 at 11:44
0

Use bitwise logic:

print("Is Power of two: ", (x&(x-1)==0))

The main idea is that any number which is a power of two, e.g., 8 is saved as 1000 in binary logic. When you subtract 1 from it, you get 7, i.e., 0111. Performing bitwise AND of these two numbers, i.e., 1000 & 0111 would result in zero. This holds true for any integer which is a (positive) power of two.

Note: This works on positive integers, so please add code to make sure that the number is int before using this logic.

Frida Schenker
  • 1,219
  • 1
  • 9
  • 14