Binary to Decimal
Recibes una cadena s que representa un número no negativo en binario, usando solo los caracteres 0 y 1. Devuelve el valor de ese número como un entero normal. La cadena no tiene ceros iniciales, excepto en el caso del número cero, que es el único carácter 0.
Función
- sstring
- los dígitos binarios del número
- Devuelveinteger
- el valor de s como un entero
Restricciones
1 ≤ s.length ≤ 31scontiene solo0y1.scomienza con1, a menos quessea"0".- Lee los dígitos tú mismo en lugar de llamar a una conversión de base integrada.
Ejemplos
- Entrada
- s = "1101"
- Salida
- 13
- Explicación
- Al leer de derecha a izquierda, las posiciones valen 1, 2, 4 y 8.
1101tiene unos en las posiciones correspondientes a 8, 4 y 1, y8 + 4 + 1 = 13.
- Entrada
- s = "0"
- Salida
- 0
- Explicación
- Un solo
0no tiene ningún 1 en ninguna posición, así que su valor es0.
- Entrada
- s = "10000000"
- Salida
- 128
- Explicación
- El único 1 tiene siete 0 a su derecha, así que ocupa el lugar que vale
2^7 = 128.
+16 pruebas ocultas al enviar
Para ir más allá
¿Puedes leer un número escrito en cualquier base del 2 al 16 con el mismo bucle, donde las letras a a f representan los dígitos del 10 al 15?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
En decimal, las cifras de
347valen 300, 40 y 7. ¿Cuánto vale cada cifra binaria?El dígito binario situado más a la derecha vale 1, y cada paso hacia la izquierda duplica el valor posicional: 1, 2, 4, 8 y así sucesivamente. El número es la suma de los valores posicionales que contienen un 1.
Puedes evitar calcular potencias: lee de izquierda a derecha y, por cada dígito, establece el valor acumulado al doble de sí mismo más ese dígito. Después del último dígito, el valor acumulado es la respuesta.
Solución
Cada dígito binario representa una potencia de dos, determinada por lo lejos que está del extremo derecho. Puedes sumar esas potencias empezando por la derecha, o leer la cadena desde la izquierda y duplicar el valor en cada paso. El bucle de duplicación nunca calcula una potencia y es el mismo bucle que usas para leer texto decimal, con 2 en lugar de 10.
Sumar los valores posicionales de derecha a izquierda
Intuición
El dígito más a la derecha vale 1, el siguiente 2, después 4, 8 y así sucesivamente, duplicándose en cada paso hacia la izquierda. El número es la suma de los valores posicionales que tienen un 1. Así que recorre los caracteres desde el último hasta el primero, mantén el valor posicional actual en power y súmalo cada vez que el dígito sea 1.
Para 1101 encuentras 1 (suma 1), 0 (omite 2), 1 (suma 4) y 1 (suma 8), lo que da un total de 13. Cada dígito se visita una vez, así que el bucle tarda O(n) y utiliza dos números de memoria.
Vigila el tamaño de power. Para una cadena de 31 dígitos, alcanza 2^30 en el último dígito y después se duplica una vez más hasta 2^31, lo cual no cabe en un entero con signo de 32 bits. Mantén power en una variable de 64 bits o deja de duplicarlo después del último dígito.
Algoritmo
- Establece
total = 0ypower = 1. - Recorre la cadena desde su último carácter hasta el primero.
- Si el carácter es
1, sumapoweratotal. - Duplica
powerantes de avanzar un lugar hacia la izquierda. - Devuelve
total.
def toDecimal(s):
total = 0
power = 1 # the place value of the rightmost digit
for i in range(len(s) - 1, -1, -1):
if s[i] == "1":
total += power
power *= 2
return totalDuplica y suma desde la izquierda
Intuición
Lee la cadena de izquierda a derecha y conserva value, el número representado por los dígitos leídos hasta el momento. Al añadir un dígito binario más, cada dígito anterior se desplaza una posición a la izquierda, lo que duplica su valor, y después se añade el nuevo dígito. Así que cada paso es value = value * 2 + digit.
Para 1101, value toma los valores 1, después 1 * 2 + 1 = 3, después 3 * 2 + 0 = 6 y, por último, 6 * 2 + 1 = 13. Cada prefijo de la cadena es un número binario más pequeño, y el bucle conserva exactamente ese número, así que después del último dígito contiene el valor completo.
El valor nunca supera el resultado final, así que, para una cadena de 31 dígitos, se mantiene dentro de 2^31-1 y basta con un entero de 32 bits. El dígito es el código del carácter menos el código de '0', lo que convierte '1' en 1 y '0' en 0. Esta es la forma estándar de analizar un número a partir de texto en cualquier base.
Algoritmo
- Establece
value = 0. - Para cada carácter, de izquierda a derecha, conviértelo en un dígito restando el código de
'0'. - Establece
value = value * 2 + digit. - Devuelve
value.
def toDecimal(s):
value = 0
for ch in s:
# Shift the digits read so far one place left, then add the new one.
value = value * 2 + (ord(ch) - ord("0"))
return value
Errores comunes y casos límite
La mayoría de las respuestas incorrectas se deben a la dirección del recorrido o al tipo del dígito.
- Asignar al dígito más a la izquierda el valor posicional 1. Los valores posicionales empiezan por el extremo derecho, así que recorre la cadena desde el último carácter o usa el bucle de duplicación desde la izquierda.
- Sumar el carácter en lugar del dígito. En muchos lenguajes,
'1'es el número 49, así quevalue * 2 + '1'es demasiado grande. Primero, resta'0'. - Desbordar el valor posicional. Duplicar
powerdespués del dígito 31 da2^31, que desborda el valor o provoca un fallo en un entero de 32 bits. - Calcular cada valor posicional con una función de potencia de punto flotante. En C, C++ y Java,
pow(2, k)devuelve undouble, y el resultado debe volver a convertirse en un entero.
Preguntas frecuentes4
¿Cómo conviertes un número binario a decimal?
Asigna a cada dígito un valor posicional: 1 para el de más a la derecha, después 2, 4, 8 y así sucesivamente hacia la izquierda. Suma los valores posicionales de los dígitos que son 1. Para 1101, eso es 8 + 4 + 1 = 13.
¿Por qué funciona duplicar el valor?
Escribir un dígito más al final de un número binario desplaza cada dígito anterior un lugar a la izquierda, y cada posición vale el doble que la que está a su derecha. Así que el valor anterior se duplica, y el nuevo dígito suma 0 o 1. Repetir esto desde el primer dígito hasta el último construye el número completo.
¿Cuál es la complejidad temporal de convertir de binario a decimal?
Ambos bucles visitan cada uno de los n caracteres una vez, así que tardan O(n). Mantienen solo uno o dos números, lo que supone un espacio adicional de O(1). Para una cadena de 31 caracteres, son 31 pasos.
¿Puedes convertir de binario a decimal con desplazamientos de bits?
Sí. value << 1 duplica el valor y | digit establece el bit menos significativo, así que value = (value << 1) | digit hace lo mismo que value * 2 + digit. La forma con desplazamiento deja claro que estás moviendo bits, mientras que la forma aritmética también funciona para bases distintas de 2.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def toDecimal(s):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
s = "1101"
Esperado
13