Decimal to Binary

Q: ¿Puedes convertir a binario usando operaciones bit a bit en lugar de dividir?

Sí. n & 1 da el bit menos significativo y n >> 1 lo descarta, lo que equivale a n % 2 y n / 2 para números no negativos. El bucle y la inversión siguen siendo iguales. La división es más fácil de explicar, mientras que la versión con desplazamiento es común en el código de bajo nivel.

PrincipianteMatemáticas y simulación Manipulación de bits

+10

Se te da un entero no negativo n. Devuelve su representación binaria como una cadena de 0 y 1, sin ceros iniciales. El único número cuya respuesta empieza con 0 es el cero, que se escribe "0".

Función

toBinary(n: integer) → string

ninteger: el número que se va a convertir
Devuelvestring: los dígitos binarios de n como una cadena

Restricciones

0 ≤ n ≤ 2³¹-1
Construye la cadena tú mismo en lugar de llamar a una conversión de base integrada.

Ejemplos

Entrada: n = 13
Salida: "1101"
Explicación: 13 = 8 + 4 + 1. Las posiciones correspondientes a 8, 4, 2 y 1 contienen 1, 1, 0 y 1, lo que se lee 1101.

Entrada: n = 0
Salida: "0"
Explicación: El cero no tiene bits activados, pero la respuesta sigue necesitando un dígito, así que es "0" en lugar de una cadena vacía.

Entrada: n = 64
Salida: "1000000"
Explicación: 64 es 2^6, un único 1 en la posición de los 64 seguido de seis 0s para las posiciones del 32 al 1.

+16 pruebas ocultas al enviar

Para ir más allá

¿Puedes convertir n a cualquier base del 2 al 16 con el mismo bucle, usando las letras a a f para los dígitos mayores que 9?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un número binario es una suma de potencias de dos, y cada dígito indica si una potencia forma parte de la suma. Puedes determinar los dígitos desde el más significativo restando potencias de dos, o leerlos desde el menos significativo como los restos de divisiones repetidas entre 2. El bucle de división es el método estándar: no tiene que encontrar primero la potencia más grande y funciona de la misma manera para cualquier base.

Resta potencias de dos desde la parte superior

Intuición

Así es como se convierte a mano. Encuentra la mayor potencia de dos que cabe en n; ese es el primer dígito, un 1. Después, baja una potencia a la vez. Si la potencia todavía cabe en lo que queda, escribe 1 y réstala; de lo contrario, escribe 0.

Para 13, la mayor potencia es 8. Escribe 1 y conserva 5. Después, 4 cabe (1, conserva 1), 2 no cabe (0) y 1 cabe (1). Los dígitos se leen 1101. El primer dígito siempre es un 1, así que no puede haber ceros a la izquierda.

Encontrar la mayor potencia requiere cuidado. Duplicar power hasta que supere n provoca un desbordamiento de un entero de 32 bits cuando n ≥ 2^30, porque la siguiente potencia es 2^31. Duplicar solo mientras power ≤ n / 2 se detiene en la potencia correcta sin sobrepasar nunca n. Un número de 31 bits requiere 31 pasos, lo que es O(log n).

Algoritmo

Si n es 0, devuelve "0".
Inicia power en 1 y duplícalo mientras power ≤ n / 2.
Mientras power > 0: si n ≥ power, añade 1 y resta power de n; de lo contrario, añade 0.
Reduce power a la mitad y repite.
Devuelve los dígitos que añadiste.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

División repetida entre 2

Intuición

El último dígito binario de n indica si n es impar, lo cual se obtiene con n % 2. Al dividir entre 2 y descartar el resto, cada dígito se desplaza un lugar a la derecha, así que el siguiente dígito pasa a ser el último. Repite el proceso hasta que no quede nada y recopilarás todos los dígitos, empezando por el menos significativo.

Para 13: 13 deja un resto de 1, 6 deja 0, 3 deja 1 y 1 deja 1; después, el número es 0. Los restos en orden son 1, 0, 1, 1; al invertirlos, se leen 1101. El bucle se detiene cuando el número llega a 0, así que el dígito más significativo que escribe siempre es un 1 y no aparece ningún cero inicial. El cero en sí nunca entra en el bucle, por eso necesita su propia comprobación.

Cada paso reduce a la mitad el número, así que un valor de 31 bits requiere 31 pasos; el tiempo es O(log n) y la cadena de dígitos ocupa O(log n) espacio.

Algoritmo

Si n es 0, devuelve "0".
Mientras n > 0, añade n % 2 como dígito y establece n en n / 2, redondeado hacia abajo.
Invierte los dígitos, porque salieron primero los de menor valor.
Devuélvelos como una cadena.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Errores comunes y casos límite

El bucle es corto, y la mayoría de las respuestas incorrectas se deben a sus dos extremos.

Devolver una cadena vacía para 0. El bucle de división no se ejecuta con cero, así que compruébalo primero.
Olvidarse de invertir el orden. Los residuos aparecen primero con el dígito menos significativo, así que 6 se obtiene como 011 en lugar de 110.
Usar / en un lenguaje donde devuelve una fracción, como JavaScript, Lua o PHP. 13 / 2 debe convertirse en 6, así que redondea hacia abajo o usa la división entera.
Construir la potencia más grande duplicando hasta superar n. Para n = 2^31-1, la siguiente potencia, 2^31, no cabe en un entero de 32 bits.
Reservar muy poco espacio en C. Un número de 31 bits necesita 31 caracteres más el '\0' terminador.

Preguntas frecuentes4

¿Cómo conviertes un número decimal a binario?

Divide el número entre 2 una y otra vez, anotando cada resto, hasta que el número llegue a 0. Lee los restos del último al primero. Para 13, los restos son 1, 0, 1, 1, así que 13 en binario es 1101.

¿Por qué se leen los restos en orden inverso?

La primera división entre 2 te indica si el número es impar, que es el último dígito binario. Cada división posterior revela el siguiente dígito hacia la izquierda. Así que los restos se obtienen empezando por el dígito menos significativo, y los inviertes para escribir el número de la forma habitual.

¿Cuál es la complejidad temporal de convertir decimal a binario?

Cada paso reduce el número a la mitad, así que el bucle se ejecuta una vez por cada dígito binario, es decir, aproximadamente log2(n) veces. Eso supone un tiempo de O(log n), y la cadena de respuesta ocupa un espacio de O(log n). Para un entero de 32 bits, esto requiere como máximo 31 pasos.

¿Puedes convertir a binario usando operaciones bit a bit en lugar de dividir?

Sí. n & 1 da el bit menos significativo y n >> 1 lo descarta, lo que equivale a n % 2 y n / 2 para números no negativos. El bucle y la inversión siguen siendo iguales. La división es más fácil de explicar, mientras que la versión con desplazamiento es común en el código de bajo nivel.

Python

def toBinary(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

n = 13

Esperado

"1101"