Binary to Decimal

Q: Qual é a complexidade de tempo da conversão de binário para decimal?

Ambos os loops percorrem cada um dos n caracteres uma vez, então levam tempo O(n) . Eles mantêm apenas um ou dois números, o que corresponde a espaço extra O(1) . Para uma string de 31 caracteres, são 31 etapas.

Q: Você consegue converter binário para decimal usando deslocamentos de bits?

Sim. value << 1 dobra o valor e | digit define o bit menos significativo, então value = (value << 1) | digit faz o mesmo que value * 2 + digit . A forma com deslocamento deixa claro que você está movendo bits, enquanto a forma aritmética também funciona para bases diferentes de 2.

InicianteMatemática e simulação Manipulação de bits

+10

Você recebe uma string s que representa um número não negativo em binário, usando apenas os caracteres 0 e 1. Retorne o valor desse número como um inteiro comum. A string não tem zeros à esquerda, exceto no caso do número zero, que é representado pelo único caractere 0.

Função

toDecimal(s: string) → integer

sstring: os dígitos binários do número
Retornainteger: o valor de s como um número inteiro

Restrições

1 ≤ s.length ≤ 31
s contém apenas 0 e 1.
s começa com 1, a menos que s seja "0".
Leia os dígitos por conta própria em vez de chamar uma conversão de base integrada.

Exemplos

Entrada: s = "1101"
Saída: 13
Explicação: Lendo da direita para a esquerda, as posições valem 1, 2, 4 e 8. 1101 tem 1s nas posições correspondentes a 8, 4 e 1, e 8 + 4 + 1 = 13.

Entrada: s = "0"
Saída: 0
Explicação: Um único 0 não tem nenhum 1 em nenhuma posição, então seu valor é 0.

Entrada: s = "10000000"
Saída: 128
Explicação: O único 1 tem sete 0s à sua direita, então ele está na posição que vale 2^7 = 128.

+16 testes ocultos ao enviar

Para ir além

Você consegue ler um número escrito em qualquer base de 2 a 16 com o mesmo loop, em que as letras a a f representam os dígitos de 10 a 15?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada dígito binário representa uma potência de dois, determinada pela distância até a extremidade direita. Você pode somar essas potências da direita para a esquerda ou ler a sequência da esquerda para a direita e dobrar o valor a cada etapa. O loop de duplicação nunca calcula uma potência e é o mesmo loop que você usa para ler texto decimal, com 2 no lugar de 10.

Some os valores posicionais da direita

Intuição

O dígito mais à direita vale 1, o seguinte vale 2, depois 4, 8 e assim por diante, dobrando a cada passo para a esquerda. O número é a soma dos valores posicionais que contêm um 1. Portanto, percorra da última posição até a primeira, mantenha o valor posicional atual em power e some-o sempre que o dígito for 1.

Para 1101, você encontra 1 (some 1), 0 (ignore 2), 1 (some 4) e 1 (some 8), totalizando 13. Cada dígito é visitado uma vez, então o loop leva O(n) de tempo e usa dois números de memória.

Fique atento ao tamanho de power. Para uma string de 31 dígitos, ele chega a 2^30 no último dígito e então é dobrado mais uma vez para 2^31, que não cabe em um inteiro com sinal de 32 bits. Mantenha power em uma variável de 64 bits ou pare de dobrá-lo depois do último dígito.

Algoritmo

Defina total = 0 e power = 1.
Percorra a string do último caractere ao primeiro.
Se o caractere for 1, some power a total.
Dobre power antes de avançar uma posição à esquerda.
Retorne 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 total

Dobrar e somar da esquerda

Intuição

Leia a string da esquerda para a direita e mantenha value, o número representado pelos dígitos lidos até então. Acrescentar mais um dígito binário desloca cada dígito anterior uma posição para a esquerda, dobrando seu valor, e depois adiciona o novo dígito. Assim, cada etapa é value = value * 2 + digit.

Para 1101, value assume os valores 1, depois 1 * 2 + 1 = 3, depois 3 * 2 + 0 = 6 e, por fim, 6 * 2 + 1 = 13. Cada prefixo da string é um número binário menor, e o loop mantém exatamente esse número; portanto, após o último dígito, ele contém o valor completo.

O valor nunca ultrapassa a resposta final, então, para uma string de 31 dígitos, ele permanece dentro de 2^31-1, e um inteiro de 32 bits é suficiente. O dígito é o código do caractere menos o código de '0', o que transforma '1' em 1 e '0' em 0. Esta é a maneira padrão de converter um número a partir de texto em qualquer base.

Algoritmo

Defina value = 0.
Para cada caractere, da esquerda para a direita, transforme-o em um dígito subtraindo o código de '0'.
Defina value = value * 2 + digit.
Retorne 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

Armadilhas e casos extremos

A maioria das respostas erradas resulta do sentido da leitura ou do tipo do dígito.

Atribuir ao dígito mais à esquerda o valor posicional 1. Os valores posicionais começam na extremidade direita, então percorra a sequência a partir do último caractere ou use o loop de duplicação da esquerda para a direita.
Somar o caractere em vez do dígito. Em muitas linguagens, '1' é o número 49, então value * 2 + '1' resulta em um valor muito maior. Subtraia '0' primeiro.
Exceder o limite do valor posicional. Duplicar power depois do 31º dígito resulta em 2^31, que dá a volta ou causa uma falha em um inteiro de 32 bits.
Calcular cada valor posicional usando uma função de potência de ponto flutuante. Em C, C++ e Java, pow(2, k) retorna um double, e o resultado precisa ser convertido de volta para um inteiro.

Perguntas frequentes4

Como converter binário para decimal?

Atribua um valor posicional a cada dígito: 1 para o mais à direita, depois 2, 4, 8 e assim por diante em direção à esquerda. Some os valores posicionais dos dígitos que são 1. Para 1101, isso é 8 + 4 + 1 = 13.

Por que dobrar o valor funciona?

Escrever mais um dígito no final de um número binário desloca cada dígito anterior uma posição para a esquerda, e cada posição vale o dobro da posição à sua direita. Assim, o valor antigo dobra, e o novo dígito acrescenta 0 ou 1. Repetir isso do primeiro ao último dígito constrói o número inteiro.

Qual é a complexidade de tempo da conversão de binário para decimal?

Ambos os loops percorrem cada um dos n caracteres uma vez, então levam tempo O(n). Eles mantêm apenas um ou dois números, o que corresponde a espaço extra O(1). Para uma string de 31 caracteres, são 31 etapas.

Você consegue converter binário para decimal usando deslocamentos de bits?

Sim. value << 1 dobra o valor e | digit define o bit menos significativo, então value = (value << 1) | digit faz o mesmo que value * 2 + digit. A forma com deslocamento deixa claro que você está movendo bits, enquanto a forma aritmética também funciona para bases diferentes de 2.

Python

def toDecimal(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "1101"

Esperado