Primeiramente, como havia citado no comentário, números binários são compostos pela base 2.
Este código em particular achei bem interessante a forma como foi feita. Não sou o melhor cara para fazer uma explicação mas tentarei.
Números binários são compostos de 1s e 0s. Cada digito de um número binário representa o "ligado" e "desligado". Cada digíto ligado, o valor somatório aumenta em 1x2^n.
Ou seja, para um agrupamento de 4 dígitos temos o valor de, até, 15 em decimal.
1111 = 1x2^3 + 1x2^2 + 1x2^1 + 1x2^0 = 15
Para o valor de 1001, por exemplo:
1001 = 1x2^3 + 0x2^2 + 0x2^1 + 1x2^0 = 9
Note que quando o valor é 0, multiplicamos por 2^n por 0.
Então, o que o algoritmo que você trouxe faz é o contrário.
No primeiro loop, que é o seguinte:
int power = 1;
while (power <= n/2)
power *= 2;
O objetivo deste loop é descobrir o maior valor de bit ativo que podemos ter. Ele já assume que todo o valor de entrada seja de, pelo menos, um digito. Ou seja, pelo menos o primeiro digito vai ser 0 ou 1, por isso o power = 1
.
Cada passagem pelo power *= 2
significa um digito para a esquerda.
Imagine a entrada 18 no seu programa.
0001 = 1 - ignorado pois sempre teremos uma iteração.
0010 = 2
0100 = 4
1000 = 8
10000 = 16
100000 = 32
Neste caso, nós não queremos o valor de 32 porque é maior que nosso valor decimal, ou seja, se este digito virasse 1 (ou fosse ligado) seria somado 32 ao nosso montante, resultando em um valor incorreto.
A partir deste momento, sabemos que teremos que fazer 4 iterações para encontrar o valor 18.
- Checa se o valor de power > 0
- Checa o valor atual for menor que o valor do digito correspondente
- Se for verdadeiro, quer dizer que o bit está desligado
- Se for falso, quer dizer que o bit está ligado
- Escrevemos 1
- Diminuímos do valor total o valor do digito correspondente
- Divide o valor do digito correspondente por 2.
- Repete
Imagine agora o algoritmo rodando com o valor 5 (fica menor a repetição).
- Seta
power=1
- Verifica se
power=1
é menor ou igual que 5 / 2 = 2
(lembre-se que está trabalhando com inteiros)
- Multiplica
power=1
por 2. Temos power=2
.
- Verifica se
power=2
é menor ou igual que 5 / 2 = 2
- Multiplica
power=2
por 2. Temos power=4
.
- Verifica se
power=4
é menor ou igual que 5 / 2 = 2
- Sai do loop
Neste caso, temos 3 iterações
Verifica se power=4
e maior que 0
- Verifica se
value=5
é menor que `power=4'
- Não é verdadeiro, neste caso, o bit não está ligado
- Escreve 1 em tela (bit ligado)
- Diminui de
value=5
o valor de power=4
resultando em value=1
.
- Divide o valor de
power=4
por 2 resultando em power=2
(queremos o bit da direita)
Verifica se power=2
e maior que 0
- Verifica se
value=1
é menor que power=4
- Escreve 0, pois este bit não está ligado
- Divide o valor de
power=2
por 2 resultando em power=1
Verifica se power=1
e maior que 0
- Verifica se
value=1
é menor que power=1
- Não é verdadeiro, neste caso, o bit não está ligado
- Escreve 1 em tela (bit ligado)
- Diminui de
value=1
o valor de power=1
resultando em value=0
.
- Divide o valor de
power=1
por 2 resultando em power=0
Verifica se power=0
é maior que 0
- Sai do loop
Neste caso, cada escrita resultou em 101 o que significa o número 5, como desejamos.
Resumindo
Veja que a iteração começa checando cada bit da esquerda pra direita.
Se o número é 5, através do primeiro loop descobre que serão, no máximo, 3 digitos que participam deste número, isto porque se o 4 digito for ligado resultaria num número maior que 5 (já que seu valor correspondente é 8).
Então, verifica o 3° bit que tem como valor 4. Se ele for maior ou igual que o valor desejado, ele está ligado, ou seja, compondo o número 5. Como o número faz parte, ele é ligado (digitando 1 em tela) e diminuímos do valor 5 o valor correspondente, restando 1.
Verifica o 2° bit que tem como valor 2. Se ele for maior ou igual que o valor desejado, ele está ligado, ou seja, compondo o número 5. Neste caso, ele é menor (já que o restante foi 1), então, o bit não está ligado e não compõe o número.
Verifica o 1° bit que tem como valor 1. Se ele for maior ou igual que o valor desejado, ele está ligado, ou seja, compondo o número 5. Neste caso, ele é igual, ou seja, o valor correspondente a aquele bit compõe o número 5. Diminuímos do valor 1 que temos atualmente pelo valor correspondente, restando 0.
Sendo assim, temos o valor de 4 + 1 formando o número 5.
Se for familiarizado com C#, dê uma olhada neste código em execução.
static void Main(string[] args)
{
int value = Int32.Parse(Console.ReadLine());
StringBuilder binary = new StringBuilder();
int totalBit = 1;
int power = 1;
while (power <= (value / 2))
{
power *= 2;
Console.WriteLine($"{ power } pode fazer parte de { value }");
totalBit++;
}
int total = 0;
int bit = totalBit;
while (power > 0)
{
if (value < power)
{
binary.Append("0");
Console.WriteLine($"O bit { bit } ({ Math.Pow(2, bit) }) nao faz parte do numero");
}
else
{
binary.Append("1");
total += power;
value -= power;
Console.WriteLine($"O bit de numero { bit } ({ Math.Pow(2, bit) }) faz parte do numero. Temos ate agora { total }");
}
power /= 2;
bit--;
}
Console.WriteLine(binary.ToString());
Console.ReadLine();
}
Disponível no .NET Fiddle caso queira testar.
Neste caso, você tem um pouco mais de detalhes sobre o que está ocorrendo.
[
Aliás, claro que existem outras formas de fazer a mesma coisa e de forma mais simples mas a explicação sobre o algoritmo em específico é esta.
Provavelmente minha explicação não foi muito boa já que não é meu forte mas tentei clarear um pouco as ideias para você. Caso não seja útil para alguém, posso tentar melhorá-la ou excluí-la.