Si asumimos que los problemas de sangrado son fruto de pegar el código aquí, dado que en caso contrario tendríamos un error de sintaxis. Tienes varios problemas de lógica:
Nota: Asumo por la lógica y los tests que la intención es verificar solo las potencias positivas de dos, es decir, la entrada de
la función será un entero siempre.
El operador %
, en esencia, retorna el resto de la división entera:
>>> 23 % 4
3
dado que 23 dividido entre 4 son 5 y me quedan 3 de resto.
Esto hace que tu condicional de control del while
:
number % 2 == 2
no tenga sentido y jamás se cumplirá. El resto de cualquier número al dividirlo entre 2 no puede ser 2 por definición, es siempre 0 (si la división es exacta) o 1. El while
debe terminar cuando encuentre un resto diferente de 0, porque eso indica que el número no es divisible entre 2 y, por tanto, no es una potencia de 2.
El operador //
lleva a cabo la división entera. Cuando haces
number = number // 1
estás dividiendo entre 1, la unidad es el elemento neutro de la divisón, un número dividido entre uno da como resultado el mismo número, number
nunca cambiará. Si se entra en el ciclo (la condición se cumple al iniciar la primera iteración) este será infinito. Debes dividir entre 2:
number = number // 2
El número será una potencia de dos (su unico factor es el 2) si al final del ciclo number
es 1. La última división realizada en estos casos en el ciclo es 2 // 2
que es 1 y ahí termina el ciclo dado que 1 % 2
es 1. Para los casos donde el número no es una potencia de dos, el ciclo termina con un valor de number
siempre impar y mayor a 1 (con una excepción que ahora veremos). Por lo tanto, tu condicional final debe ser:
if number == 1:
Con todo ello nos queda un caso especial que hay que resolver. Si el número de entrada es 0 tendremos un ciclo infinito. 0 % 2
es 0 y 0 // 2
es también 0 por lo que el ciclo jamás terminará. Lo más simple es agregar una condición de entrada que retorne False
para todo número menor o igual a 0.
Con todo quedaría algo así:
def is_power_of_two(number: int) -> bool:
if number <= 0:
return False
while number % 2 == 0:
number = number // 2
if number == 1:
return True
return False
O puedes eliminar el condicional final y simplemente retornar la salida de la comparación:
def is_power_of_two(number: int) -> bool:
if number <= 0:
return False
while number % 2 == 0:
number //= 2
return number == 1
Si se quiera hacer esto de forma mucho más eficiente, la respuesta está en las propiedades de la representación binaria de las potencias de dos; en la representacion de los números enteros positivos en binario solo aquellos que son potencias de dos tiene un solo bit establecido en 1 (y la posición que ocupa ese bit se corresponde con el valor del exponente):
Portencia (decimal) |
Binario (8 bits uint) |
20 = 1 |
00000001 |
21 = 2 |
00000010 |
22 = 4 |
00000100 |
23 = 8 |
00001000 |
24 = 16 |
00010000 |
25 = 32 |
00100000 |
26 = 64 |
01000000 |
27 = 128 |
10000000 |
Típicamente, se implementa aplicando un and bit a bit entre n
y n - 1
(n & (n - 1)
, que será cero para todo n != 0
que sea una potencia de dos), dado que n - 1
tendrá todos los bits en 1 menos el que es 1 en n
. No obstante, int.bit_count()
nos viene muy bien en este caso:
def is_power_of_two(number: int) -> bool:
return number > 0 and number.bit_count() == 1
La diferencia en tiempo de ejecución es muy significativa si trabajamos con potencias grandes:
n = 2 ** 231185
%%timeit
is_power_of_two_iterative_divmod(n)
7.22 s ± 8.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%%timeit
is_power_of_two_bit_count(n)
17.8 µs ± 2.6 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
if
está fuera de la función... las tabulaciones son lo que define los bloques de código en python, no puede uno inventárselas sin más!