How to get the representation of a positive integer in binary, using recursion?

Question

I searched several sites, and in none I could understand how to make a conversion code using recursion from a positive integer to binary.

I know there’s a function itoa but the challenge of the exercise is to do it recursively.

An idea of a bond I have that may be possible

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

Answer 1

For positive numbers, what we can do is successive divisions by two and write module 2 (or num & 1 to make explicit that you want the bit) in the appropriate position for this.

An interesting recursion to do this by writing in big-endian, involves returning the position to write the next desired character and, at the base of the recursion, placing the string terminator '\0', passing the current position of the string as parameter. I would particularly do this by returning the memory address, or through a structure. It would also do a public function to make the call and this in turn would care to make the recursive call and put the '\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;
}

Example of what to call:

char buff[100];
printf("to_binary_representation(%d), %s\n", 0, to_binary_representation(0, buff));

See working on ideone.

I also printed negative numbers in addition to 2.

Explanation of negative numbers

Okay, I know, the negative numbers were a plus. But they’re easy to explain and they’re pretty interesting.

As I mentioned, I am using the complement notation of 2. There are other rating possibilities, but the most usual really is complement of 2.

That reply from @ramaral explains how to get a complement number of 2:

A simple way may be to calculate the complement to 1 and add 1 as described in the entry Complement to two wikipedia.

I say it’s a simple way because it’s easy to calculate the complement of 1, just for this to apply the operation bitwise NOT at value

So, come on. Let’s take any number in binary. For example, 5, represented in 8 bits:

00000101

The complement of 1 is bitwise NOT of value:

11111010

Then, we add 1 to the final result, thus obtaining the complement of 2:

11111011

Making for 6, 7, 10 and 32 in a single step

6:

00000110
11111001
11111010

7:

00000111
11111000
11111001

10:

00001010
11110101
11110110

32:

00100000
11011111
11100000

Have you noticed that you can do it in one jump without having to do two operations? Just follow the following algorithm:

1. swipe from right to left
2. you get in the state bit1_not_found
3. after reading a bit, you move a position to the left
4. while you’re in the state bit1_not_found, repeat the bit that was read on output;
   if you read 0, place 0, if you read 1, place 1
5. while you’re in the state bit1_found, invert the bit that was read on output;
   if you read 0, place 1, if you read 1, place 0
6. if you read the character 1 and is in the state bit1_not_found, change your state to bit1_found (the printed character remains the same, only the next one will be changed)

This can be represented in the following automaton:

In the links, we have a style notation X/Y. This means that when reading the character X, the character will be printed Y and the state will be changed to what is at the tip of the arrow.

For the case of two transitions containing the same input and output states, it was represented by placing ; to separate inputs and outputs, as in 0/1 ; 1/0.

But why does it work?

Well, in even number, we have that the negation will end with several 1s, and the sequence of 1s will follow up to the position where the first connected bit of the original number is, which will be exchanged for 0. So, we have that an even number and its negation will always be of the following format:

    sequência de n 0s e um 1 no final
    _|_
   /   \
xxx10000
yyy01111
   \___/
     |
    sequência de n 1s e um 0 no final

What happens when you increase that number? Well, he’ll do the carry us n sequence numbers and, at position n+1 from right to left, carry will no longer be propagated. So, whatever the number being incremented, the following:

yyy01111
      +1
--------
yyy10000

Now, let’s add the original number to the 2:

xxx10000
yyy10000

Only bits left of 1 are modified. All others remain intact.

The demonstration for odd follows the same thought, being that in the first digit there is no carry:

    xxx1
    yyy0

    yyy0
      +1
    ----
    yyy1

    xxx1
    yyy1

The automaton is implemented in this code snippet:

// 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;
  }
}

About big-endian

The notation big-endian, is how we read Indo-Arabic numbers in English: the most significant bits are at the beginning (left). As a priori we do not know how many bits it will take to print in Portuguese, I leave to write after detecting how many bits it takes to write the number. Then the first character to be written will be the least significant, at the last position of the string.

The detection that one arrived at the last character (ie, does not need any additional information) is:

// char* __private_to_binary_representation(int n, char* print_here) {

if (n == 0) {
  return print_here;
}

Identifying the bits

The only guaranteed position that I can check the bit is the least significant. I do this using (n & 1), the operation bitwise which will return 1 or 0, as the most significant bits are zeroed by the second operand. So the representation is '1' when (n & 1) is true and '0' otherwise.

By the way, when it’s true, (n & 1) returns 1, and returns 0 otherwise. Due to the positioning of the ASCII table, '0' + 1 will result in '1', already '0' + 0 will continue '0'.

This is identified in this passage:

//char* __private_to_binary_representation(int n, char* print_here) {

(n & 1) + '0';

To always decrease the number with each recursive call, to catch the next bit, we make the recursive call by shifting the number 1 bit to the right:

n >> 1

This is equivalent to taking the whole division of the number by 2 (discarding any rest), but I wanted to make it clear that my intention is to deal with bit displacement.

The print position

The most significant data shall be printed in the leftmost position. The identification that arrived at the most significant number is right after identifying that the number ran out. As I am printing with signal, I also do the shift to keep the signal bit intact.

Because of this, the print position is passed intact to the next level of the iteration. When the time comes to return from iteration, it should be passed to the previous level which position it should print. In the base case of the recursion, when there is nothing else to print, it returns the initial print position. For all other cases, returns the position right after, a right position.

The return occurs using pointer arithmetic. A space forward is ponteiro + 1. To write at pointer position, just do *ponteiro = valor or ponteiro[0] = valor. I preferred the first way to make it clearer that I’m dealing with pointer manipulation, since the second form, with index, has an aggregated vector semantics, which I don’t want.

This is found in this code snippet:

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;
}

The first digit

As we are using complement two, the signal bit (the leftmost bit, the most significant) is 0 for positive numbers. A priori, the function that transforms the number into a binary string works for numbers positive. The transformation to negative number takes place in the next moment. So, __private_to_binary_representation returns the magnitude representation of the number, ignoring the signal bit. To indicate that it will ignore the signal bit, it is passed to that function the second print position, not the first. The absolute value of the number is also passed.

In the return of the recursive call to the original caller, we obtain the position beyond the least significant, the appropriate position to place the null terminator. We save this value and then put the null terminator value in this snippet:

char* null_terminator_pos = __private_to_binary_representation(abs(n), print_here + 1, 0);

// garantindo o final da string
(*null_terminator_pos) = '\0';

Then the number is printed in the first position '0', representing the magnitude of the number passed in complement of 2. If it is detected that the number passed is negative, run the automaton to transform the string.

Answer 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);
}

My solution is simple, but it worked for the numbers I tested. I hope you’re right and I’ve helped you. : x