Decimal to Binary

Q: Você consegue converter para binário usando operações de bits em vez de divisão?

Sim. n & 1 obtém o bit menos significativo e n >> 1 o remove, o que é equivalente a n % 2 e n / 2 para números não negativos. O loop e a inversão permanecem iguais. A divisão é mais fácil de explicar, enquanto a versão com deslocamento é comum em código de baixo nível.

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

+10

Você recebe um inteiro não negativo n. Retorne sua representação binária como uma cadeia de caracteres formada por 0 e 1, sem zeros à esquerda. O único número cuja resposta começa com 0 é o próprio zero, que é escrito "0".

Função

toBinary(n: integer) → string

ninteger: o número a converter
Retornastring: os dígitos binários de n como uma string

Restrições

0 ≤ n ≤ 2³¹-1
Crie a string por conta própria em vez de chamar uma conversão de base integrada.

Exemplos

Entrada: n = 13
Saída: "1101"
Explicação: 13 = 8 + 4 + 1. As posições de 8, 4, 2 e 1 contêm 1, 1, 0 e 1, o que resulta em 1101.

Entrada: n = 0
Saída: "0"
Explicação: Zero não tem bits definidos, mas a resposta ainda precisa de um dígito, então é "0" em vez de uma string vazia.

Entrada: n = 64
Saída: "1000000"
Explicação: 64 é 2^6, um único 1 na posição dos 64, seguido de seis 0s nas posições de 32 até 1.

+16 testes ocultos ao enviar

Para ir além

Você consegue converter n para qualquer base de 2 a 16 usando o mesmo loop, com as letras a a f para os dígitos acima de 9?

Dicas

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

0 de 3 abertas

Solução

Um número binário é uma soma de potências de dois, e cada dígito indica se uma potência faz parte da soma. Você pode determinar os dígitos de cima para baixo, subtraindo potências de dois, ou lê-los de baixo para cima como os restos de divisões sucessivas por 2. O laço de divisão é o método padrão: ele nunca precisa encontrar primeiro a maior potência e funciona da mesma forma para qualquer base.

Subtraia potências de dois do topo

Intuição

É assim que você converte manualmente. Encontre a maior potência de dois que cabe em n; esse é o primeiro dígito, um 1. Depois, desça uma potência de cada vez. Se a potência ainda couber no que restou, escreva 1 e subtraia-a; caso contrário, escreva 0.

Para 13, a maior potência é 8. Escreva 1 e fique com 5. Depois, 4 cabe (1, fique com 1), 2 não cabe (0) e 1 cabe (1). Os dígitos formam 1101. O primeiro dígito é sempre 1, então não pode aparecer nenhum zero à esquerda.

Encontrar a maior potência exige cuidado. Dobrar power até que passe de n causa um estouro de inteiro de 32 bits quando n ≥ 2^30, porque a potência seguinte é 2^31. Dobrar somente enquanto power ≤ n / 2 para na potência correta sem nunca ultrapassar n. Um número de 31 bits leva 31 etapas, o que é O(log n).

Algoritmo

Se n for 0, retorne "0".
Comece com power igual a 1 e dobre-o enquanto power ≤ n / 2.
Enquanto power > 0: se n ≥ power, acrescente 1 e subtraia power de n; caso contrário, acrescente 0.
Divida power pela metade e repita.
Retorne os dígitos que você acrescentou.

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)

Divisão repetida por 2

Intuição

O último dígito binário de n indica se n é ímpar, ou seja, n % 2. Dividir por 2 e descartar o resto desloca cada dígito uma posição para a direita, então o próximo dígito se torna o último. Repita até não sobrar nada e você terá coletado todos os dígitos, começando pelo menos significativo.

Para 13: 13 deixa resto 1, 6 deixa 0, 3 deixa 1 e 1 deixa 1; em seguida, o número é 0. Os restos, na ordem, são 1, 0, 1, 1; invertidos, formam 1101. O loop para quando o número chega a 0, então o dígito mais significativo que ele escreve é sempre 1 e nenhum zero à esquerda aparece. O próprio zero nunca entra no loop, por isso precisa de uma verificação própria.

Cada etapa divide o número pela metade, então um valor de 31 bits leva 31 etapas, tempo O(log n), e a sequência de dígitos ocupa espaço O(log n).

Algoritmo

Se n for 0, retorne "0".
Enquanto n > 0, acrescente n % 2 como um dígito e defina n como n / 2, arredondado para baixo.
Inverta os dígitos, porque eles foram obtidos do menor para o maior.
Retorne-os como uma string.

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)

Armadilhas e casos extremos

O loop é curto, e a maioria das respostas erradas vem das suas duas extremidades.

Retornar uma string vazia para 0. O loop de divisão nunca é executado para zero, então verifique-o primeiro.
Esquecer de inverter. Os restos chegam com o dígito menos significativo primeiro, então 6 resulta em 011 em vez de 110.
Usar / em uma linguagem na qual ele retorna uma fração, como JavaScript, Lua ou PHP. 13 / 2 precisa se tornar 6, então arredonde para baixo ou use divisão inteira.
Construir a maior potência dobrando até passar de n. Para n = 2^31-1, a próxima potência, 2^31, não cabe em um inteiro de 32 bits.
Alocar espaço insuficiente em C. Um número de 31 bits precisa de 31 caracteres mais o '\0' terminador.

Perguntas frequentes4

Como converter um número decimal para binário?

Divida o número por 2 repetidamente, anotando cada resto, até que o número chegue a 0. Leia os restos do último para o primeiro. Para 13, os restos são 1, 0, 1, 1, então 13 em binário é 1101.

Por que os restos são lidos na ordem inversa?

A primeira divisão por 2 informa se o número é ímpar, que é o último dígito binário. Cada divisão posterior revela o próximo dígito à esquerda. Portanto, os restos aparecem primeiro com o dígito menos significativo, e você os inverte para escrever o número da forma usual.

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

Cada etapa divide o número pela metade, então o loop é executado uma vez por dígito binário, ou seja, cerca de log2(n) vezes. Isso leva O(log n) de tempo, e a string da resposta ocupa O(log n) de espaço. Para um inteiro de 32 bits, são no máximo 31 etapas.

Você consegue converter para binário usando operações de bits em vez de divisão?

Sim. n & 1 obtém o bit menos significativo e n >> 1 o remove, o que é equivalente a n % 2 e n / 2 para números não negativos. O loop e a inversão permanecem iguais. A divisão é mais fácil de explicar, enquanto a versão com deslocamento é comum em código de baixo nível.

Python

def toBinary(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

n = 13

Esperado

"1101"