Para números positivos, o que podemos fazer é divisões sucessivas por dois e escrever o módulo 2 (ou num & 1
para deixar explícito que se quer o bit) na posição adequada para isso.
Uma recursão interessante para fazer isso, escrevendo em big-endian, envolve retornar a posição para escrever o próximo caracter desejado e, na base da recursão, colocar o terminador de string '\0'
, passando a posição atual da string como parâmetro. Eu particularmente faria isso retornando o endereço de memória, ou através de uma estrutura. Também faria uma função pública para fazer a chamada e essa, por sua vez, se preocuparia em fazer a chamada recursiva e colocar o '\0'
.
char* __private_to_binary_representation(int n, char* print_here) {
if (n == 0) {
return print_here;
}
print_here = __private_to_binary_representation(n >> 1, print_here);
(*print_here) = (n & 1) + '0';
return print_here + 1;
}
char* to_binary_representation(int n, char* print_here) {
int is_negative = n < 0? 1: 0;
// primeiro, preencho o valor absoluto do número, então o primeiro bit sempre será 0
char* null_terminator_pos = __private_to_binary_representation(abs(n), print_here + 1, 0);
print_here[0] = '0';
// garantindo o final da string
(*null_terminator_pos) = '\0';
if (is_negative) {
char* bit_check;
int bit1_found = 0;
for (bit_check = null_terminator_pos - 1; bit_check >= print_here; bit_check--) {
// troca os bits na representação de complemento de 2
if (bit1_found) {
(*bit_check) = (*bit_check) == '1'? '0': '1';
} else if ((*bit_check) == '1') {
bit1_found = 1;
}
}
}
return print_here;
}
Exemplo de como chamar:
char buff[100];
printf("to_binary_representation(%d), %s\n", 0, to_binary_representation(0, buff));
Veja funcionando no ideone.
Apoveitei e imprimi também números negativos em complemento de 2.
Explicação dos números negativos
Ok, eu sei, os números negativos foram um extra. Mas eles são fáceis de explicar e são bem interessantes.
Conforme eu mencionei, estou usando a notação complemento de 2. Existem outras possibilidades de notação, porém a mais usual realmente é complemento de 2.
Essa resposta do @ramaral explica como obter um número em complemento de 2:
Uma forma simples poderá ser calcular o complemento para 1 e somar 1 como descrito na entrada Complemento para dois da wikipedia.
Digo que é uma forma simples porque é fácil calcular o complemento de 1, bastando para isso aplicar a operação bitwise NOT ao valor
Então, vamos lá. Peguemos um número qualquer em binário. Por exemplo, 5, representado em 8 bits:
00000101
O complemento de 1 é o bitwise NOT do valor:
11111010
Então, somamos 1 ao resultado final, obtendo assim o complemento de 2:
11111011
Fazendo para 6, 7, 10 e 32, em um passo único
6:
00000110
11111001
11111010
7:
00000111
11111000
11111001
10:
00001010
11110101
11110110
32:
00100000
11011111
11100000
Notou que dá para fazer em um salto só, sem precisar fazer duas operações? Basta seguir o seguinte algoritmo:
- percorra da direita para a esquerda
- você começa no estado
bit1_not_found
- depois de ler um bit, você move uma posição para a esquerda
- enquanto você está no estado
bit1_not_found
, repita o bit que foi lido na saída;
se você leu 0
, coloque 0
, se você leu 1
, coloque 1
- enquanto você está no estado
bit1_found
, inverta o bit que foi lido na saída;
se você leu 0
, coloque 1
, se você leu 1
, coloque 0
- se você leu o caracter
1
e está no estado bit1_not_found
, mude seu estado para bit1_found
(o caracter impresso continua o mesmo, só no próximo que será alterado)
Isso pode ser representado no seguinte autômato:
Nas ligações, o que temos uma notação estilo X/Y
. Isso quer dizer que ao ler o caracter X
, vai ser impresso o caracter Y
e o estado será alterado para o que está na ponta da seta.
Para o caso de duas transições contendo os mesmos estados de entrada e saída, foi representado colocando ;
para separar as entradas e saídas, como em 0/1 ; 1/0
.
Mas por que isso funciona?
Bem, em número pares, temos que a negação terminará com vários 1s, e a sequência de 1s se seguirá até a posição onde está o primeiro bit ligado do número original, que será trocado por 0. Então, temos que um número par e sua negação sempre serão do seguinte formato:
sequência de n 0s e um 1 no final
_|_
/ \
xxx10000
yyy01111
\___/
|
sequência de n 1s e um 0 no final
O que acontece ao incrementar esse número? Bem, ele fará o carry nos n
números da sequência e, na posição n+1
da direita para a esquerda, o carry não será mais propagado. Então, qualquer que seja o número sendo incrementado, o seguinte vale:
yyy01111
+1
--------
yyy10000
Agora, comparemos o número original ao complemento de 2:
xxx10000
yyy10000
Apenas os bits a esquerda do 1 são modificados. Todos os outros permanecem intactos.
A demonstração para o ímpar segue o mesmo pensamento, sendo que logo no primeiro dígito não há carry:
xxx1
yyy0
yyy0
+1
----
yyy1
xxx1
yyy1
O autômato está implementado neste trecho de código:
// char* to_binary_representation(int n, char* print_here) {
char* bit_check;
int bit1_found = 0;
for (bit_check = null_terminator_pos - 1; bit_check >= print_here; bit_check--) {
// troca os bits na representação de complemento de 2
if (bit1_found) {
(*bit_check) = (*bit_check) == '1'? '0': '1';
} else if ((*bit_check) == '1') {
bit1_found = 1;
}
}
Sobre big-endian
A notação big-endian, é o modo como lemos números indo-arábicos em português: os bits mais significantes ficam no começo (a esquerda). Como a priori não sabemos quantos bits serão necessários, para imprimir do modo legível em português, eu deixo para escrever após detectar quantos bits são necessários para escrever o número. Então, o primeiro caracter a ser escrito será o menos significativo, na última posição da string.
A detecção de que se chegou no último caracter (ie, não precisa de nenhuma informação adicional) é:
// char* __private_to_binary_representation(int n, char* print_here) {
if (n == 0) {
return print_here;
}
Identificando os bits
A única posição garantida que eu posso verificar o bit é a menos significativa. Faço isso usando (n & 1)
, a operação bitwise que vai retornar 1 ou 0, pois os bits mais significativos são zerados pelo segundo operando. Então, a representação é '1'
para quando (n & 1)
for verdade e '0'
para o caso contrário.
Por sinal, quando é verdade, (n & 1)
retorna 1, e retorna 0 caso contrário. Devido ao posicionamento da tabela ASCII, '0' + 1
vai resultar em '1'
, já '0' + 0
continuará '0'
.
Isso é identificado nesse trecho:
//char* __private_to_binary_representation(int n, char* print_here) {
(n & 1) + '0';
Para ficar sempre diminuindo o número a cada chamada recursiva, para pegar o próximo bit, fazemos a chamada recursiva deslocando o número 1 bit para a direita:
n >> 1
Isso é equivalente a pegar a divisão inteira do número por 2 (descartando eventual resto), mas quis deixar mais claro que a minha intenção é tratar de deslocamento de bits.
A posição de impressão
O dado mais significativo deve ser impresso na posição mais a esquerda. A identificação que chegou no número mais significativo é logo após identificar que acabou o número. Como estou imprimindo com sinal, eu também faço o shift para manter o bit de sinal intacto.
Por conta disso posição de impressão é passada intacta para o nível seguinte da iteração. Ao chegar o momento de retornar da iteração, deve ser passado ao nível anterior qual a posição que ele deve imprimir. No caso base da recursão, quando não há mais nada a ser impresso, retorna a posição de impressão inicial. Para todos os outros casos, retorna a posição logo a seguir, uma posição a direita.
O retorno se dá usando aritmética de ponteiros. Um espaço adiante é ponteiro + 1
. Para escrever na posição do ponteiro, basta fazer *ponteiro = valor
ou ponteiro[0] = valor
. Eu preferi a primeira maneira para tornar mais claro que estou tratando de manipulação de ponteiros, já que a segunda forma, com índice, tem uma semântica agregada de vetor, o que não desejo.
Isso se encontra nesse trecho de código:
char* __private_to_binary_representation(int n, char* print_here) {
if (n == 0) {
return print_here;
}
print_here = __private_to_binary_representation(n >> 1, print_here);
(*print_here) = (n & 1) + '0';
return print_here + 1;
}
O primeiro dígito
Como estamos usando complemento de dois, o bit de sinal (o bit mais a esquerda, o mais significativo) é 0
para números positivos. A priori, a função que transforma o número para uma string binária funciona para números positivos. A transformação para número negativo se dá no próximo momento. Então, __private_to_binary_representation
devolve a representação da magnitude do número, ignorando o bit de sinal. Para indicar que ele irá ignorar o bit de sinal, é passado para essa função a segunda posição de impressão, não a primeira. Também é passado o valor absoluto do número.
No retorna da chamada recursiva para o chamador original, obtemos a posição além da menos significativa, a posição adequada para se colocar o terminador nulo. Guardamos esse valor e então colocamos o valor terminador nulo nesse trecho:
char* null_terminator_pos = __private_to_binary_representation(abs(n), print_here + 1, 0);
// garantindo o final da string
(*null_terminator_pos) = '\0';
Então, é impresso na primeira posição o número '0'
, representando a magnitude do número passado em complemento de 2. Caso seja detectado que o número passado é negativo, rodamos o autômato para transformar a string.