When is it acceptable to induce an infinite loop?-CodePudding

Stumbled across this coding challenge today and, the goal is to check if n is a power of two. Not all too happy with my solution although it does seem pass all tests.

For one, it doesn't really seem to match the Pseudo code written before it and when trying to compare n to a number greater than those used in the tests ie: while n < 10: I am hit with an infinite loop.

Having trouble wrapping my head around this one!

I've heard of purposefully inducing an indefinite loop; is this some sort of abstract rendition of that concept?

def is_power_of_two(n):
  # Check if the number can be divided by two without a remainder
  while n % 2 != n:
    n = n / 2
  # If after dividing by two the number is 1, it's a power of two
  if n == 1:
    return True
  return False

print(is_power_of_two(0)) # Should be False
print(is_power_of_two(1)) # Should be True
print(is_power_of_two(8)) # Should be True
print(is_power_of_two(9)) # Should be False

CodePudding user response：

The code seems to work well for many inputs, but it relies on floating point numbers, by applying a (non-integer) division by 2. If in the end this nicely ends up with n being 1, then indeed the original number was a power of 2.

However, because of floating point limitations, this will break far large enough inputs. You'll get false positives.

For instance:

is_power_of_two((1<<80)   1)

This should return False, as there are clearly two 1-bits in this number. But your function will return True, as if the input had been 1<<80.

To get a correct implementation, you should use integer division (//) and keep looping as long as the remainder is 0.

And to the topic of infinite loops: it could not loop infinitely for because n becomes smaller by the division, and eventually, it will get below the value of 2, when n % 2 == n.

Even when n is negative... in that case it will remain negative by the division, but again because of floating point limitations, the division will eventually give 0, and at that moment the loop condition is fulfilled.

The integer-based version, could loop forever if the input is 0, and would need protection for that case. We can use the opportunity to also capture negative inputs:

  if n <= 0:
    return False
  while n % 2 == 0:
    n = n // 2

Now the above test case will return the correct result.

CodePudding user response：

This should work:

def is_power_of_two(n):
    while n > 1:
        n /= 2
    return n == 1

print(is_power_of_two(0)) # False
print(is_power_of_two(1)) # True
print(is_power_of_two(8)) # True
print(is_power_of_two(9)) # False

CodePudding user response：

This algorithm can actually be solved without a loop at all.

If you choose to use bit shifting, the algorithm can look like:

def is_power_two(n):
    if n < 2:
        return False
    return not n ^ (1 << int(n).bit_length() - 1)

Give a number n, say 8; as the number 8 occupies 4 bits, you can use a bit shift of 1 << number of bits - 1 along with an XOR of the number. If the number is a power of two, zero (False) is returned, otherwise a non-zero value (True) is returned.

Testing:

for i in range(65):
    print(i, is_power_two(i))

0 False
1 False
2 True
3 False
4 True
5 False
6 False
7 False
8 True
9 False
...
62 False
63 False
64 True