Algoritmos e Estruturas de Dados

Converter Números Decimais em Binário

Compreender como converter números decimais (os que utilizamos no dia a dia) em números binários (usados pelos computadores) é uma competência fundamental em ciência da computação. No sistema binário, cada posição de dígito representa uma potência específica de dois. Pense num número binário como forma de indicar quais potências de dois são necessárias para que a soma dessas potências corresponda ao número dado.
Número em base-10
128
64
32
16
8
4
2
1
Soma
114
0
1
1
1
0
0
1
0
114 = 64 + 32 + 16 + 2
12
0
0
0
0
1
1
0
0
12 = 8 + 4
13
0
0
0
0
1
1
0
1
13 = 8 + 4 + 1
Cada 1 na representação binária indica que a potência de dois correspondente faz parte da soma, enquanto cada 0 indica o contrário. A beleza do sistema binário está na sua simplicidade e singularidade.
💡
Cada número tem uma e apenas uma representação binária, composta por uma soma de potências de dois distintas.

Encontrar o Bit Mais à Direita

Para começar, vamos pensar em como encontrar o bit mais à direita na representação binária de um número. No sistema decimal, para descobrir o último dígito de um número, basta obter o resto da divisão por 10, normalmente expresso como % 10 nas linguagens de programação. De forma semelhante, em binário, o bit mais à direita pode ser encontrado obtendo o resto da divisão por 2, ou % 2. Isso também significa que o bit mais à direita é sempre 1 para números ímpares e 0 para números pares.
Por exemplo:
  • Para 114, o bit mais à direita é 0, pois 114 % 2 = 0.
  • Para 13, o bit mais à direita é 1, pois 13 % 2 = 1.

Deslocar um Número Binário

Depois de encontrarmos o bit mais à direita, o próximo passo é deslocar todo o número binário uma posição para a direita. Na prática, isso equivale a efetuar a divisão inteira do número por 2 (geralmente notada como / 2 em muitas linguagens de programação, ou // 2 em Python). Essa operação remove efetivamente o bit mais à direita, tornando o bit seguinte o novo bit mais à direita.
  • Ao deslocar 114 ( em binário) para a direita, obtemos , que corresponde a 114 / 2 = 57 em base-10.
  • Ao deslocar 13 ( em binário) para a direita, obtemos , que é 13 / 2 = 6 em base-10.

O Algoritmo de Conversão

Tendo em mãos essas duas operações — encontrar o bit mais à direita e deslocar o número — podemos elaborar um algoritmo simples para converter um número decimal em binário:
  1. Inicialize uma string vazia para armazenar a representação binária.
  1. Enquanto o número for maior que 0:
      • Find the rightmost bit by taking the remainder when divided by 2.
      • Add this bit to the left of your binary string.
      • Floor-divide the number by 2 to shift it to the right.
  1. Devolva a string binária se ela não estiver vazia; caso contrário, devolva 0.
Usando esse algoritmo, é possível converter qualquer número em base-10 na sua representação binária única.

Implementação Mínima

b, d = '101001101', 0   # números binário e decimal
power = 1               # Potência atual de 2 (1, 2, 4, 8, 16, ...)

for bi in b[::-1]:      # Percorrer do bit menos significativo para o mais significativo
    d += int(bi) * power
    power *= 2

print(d)
binary → decimal conversion
b, d = '', 5234         # números binário e decimal

while d > 0:            # Enquanto ainda houver bits para processar
    b = str(d % 2) + b  # Insere o bit à esquerda da string
    d //= 2             # Desloca o número para a direita

print(b if b != '' else 0)
decimal → binary conversion
 
To check your solution you need to sign in
Sign in to continue