5

Procurei por vários sites, e em nenhum eu consegui entender como fazer um código de conversão usando recursão de um inteiro positivo para binário.

Eu conheço que existe a função itoa porém o desafio do exercício é fazer de maneira recursiva.

Uma ideia de laço que eu tenho que pode ser possível

memset(&binario,NULL,10);
for(i=0;i<4;i++){
   quoc = dividendo / 2;
   resto = dividendo % 2;
   if (resto == 1) {
      binario[i] = '1';
   }
   dividendo = quoc;
}
1

2 Respostas 2

5

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:

  1. percorra da direita para a esquerda
  2. você começa no estado bit1_not_found
  3. depois de ler um bit, você move uma posição para a esquerda
  4. 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
  5. 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
  6. 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:

autômato do algoritmo acima

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.

1
  • Ok, muito obrigado, ajudou muito :) Commented 10/01/2018 às 18:05
2
#include <stdlib.h>
void binario(int n){
    if(n!=1)
        binario(n/2);
    printf("%d", n%2);
}
int main(){
    int n;
    scanf("%d%*c", &n);
    binario(n);
}

Minha solução é simples, mas deu certo para os números que eu testei. Espero que esteja certo e ter te ajudado. :x

3
  • Você imprimiu mas não obteve o valor. Sacou a diferença? Commented 10/01/2018 às 17:02
  • 1
    Funcionou, obrigado! Commented 10/01/2018 às 17:54
  • @JeffersonQuesado aposto que agora ta mais fácil pra ele entender, caso ele precise armazenar o valor é só ele fazer algumas alterações no código Commented 11/01/2018 às 10:56

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .