Hello reader, this is the first article of a series where I will be trying to recreate arithmetic operations in binary using C Lets' get into the good stuff.

What the heck am I doing exactly

Well, as I said, arithmetic operations, I will start with integers first, so the goal is to have functions for every operations (addition, division, substraction and multiplication) that would take in 2 integers and return the result of the corresponding operation. The catch is that we are not allowed to use the "built in" arithmetic operations in C, meaning this

int add(int a, int b){
  return a+b;
}

is invalid.

How ?

Binary! the way I think I can do this right now is by first converting the numbers in binary and then just perform the operation on the binary representations.

So in this first article, we are just going to tackle the first problem: how to convert an integer into it's binary representation. Well it's quite simple, simpler than I thought at least. If you are learning C like me and have currently no idea about how that could be done I suggest you try doing it by yourself and who knows, you might come up with a better implementation that mine. But here goes nothing

We know that to convert an integer into binary, we need to divide it by 2 and for each division we keep the remainder until we get a quotient of 0, then we write down the remainders in reverse order and that gives us the binary representation of that integer.

For example, if we were to convert 4 into binary, we would have the following:

4/2: 2 (remainder 0)

2/2: 1 (remainder 0)

1/2: 0 (remainder 1)

We stop when we get 0 as quotient, and we write down the remainders from down to up to get 100 and that is the binary representation of 4 ( 1 * 2^2 + 0 * 2^1 + 0 * 2^0 )

Great, now we need to translate that algorythm in C. First we need a way to store the 0s and 1s that form the binary, we also need to keep in mind that we will have to store the remainders and collect them from last to first to form the representation. When I was writing my first solution, I thought a linked list would be the best fit, I would just insert a new Node at the end of the list and when I will be done with the divisions I would just collect the values from the list already sorted the way I want it. But I actually found a simpler way (I think). The main reason I wanted to use a linked list instead of a simple array was because I didn't know that I could know the size of the binary representation of a number, but it turns out there is a formula Number of bits = ⌈log2(integer)⌉ with that formulat we can actually calculate the number of bits needed to represent an integer in binary. Great, so here is what our function look like

#include <math.h>

char *get_binary_representation(int number) {
  int number_of_bits = ceil(log2(number));
};

using the math library in C we can reproduce the formula and get the number of bits we need. Next we need to allocate enough memory to store our binary representation

#include <math.h>
#include <stdlib.h>

char *get_binary_representation(int number) {
  int number_of_bits = ceil(log2(number));
  char *representation = malloc((number_of_bits + 1) * sizeof(char));
};

Using malloc we get a contiguous space in memory to store our binary number. We add 1 to the number of bits because we will need to store the null terminator \0 at the end of the string. Next we will keep dividing our number until we find a quotient equal to 0, and while we are doing that we store the remainder in our string from the last index to the first

#include <math.h>
#include <stdlib.h>

char *get_binary_representation(int number) {
  int number_of_bits = ceil(log2(number));
  char *representation = malloc((number_of_bits + 1) * sizeof(char));
  int remainder;
  for (int i = number_of_bits - 1; i >= 0; i--) {
    remainder = number % 2;
    number = number / 2;
    char bin[2];
    sprintf(bin, "%d", remainder);
    representation[i] = *bin;
  }
  return representation;
};

There we have it, all we need now is to test it, here is the whole code

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

char *get_binary_representation(int number) {
  int number_of_bits = ceil(log2(number));
  char *representation = malloc((number_of_bits + 1) * sizeof(char));
  int remainder;
  for (int i = number_of_bits - 1; i >= 0; i--) {
    remainder = number % 2;
    number = number / 2;
    char bin[2];
    sprintf(bin, "%d", remainder);
    representation[i] = *bin;
  }
  return representation;
};

int main(int argc, char **argv) {
  char *representation = get_binary_representation(9);
  printf("%s", representation);
  free(representation)
  return 0;
}

And it works yay. Now that we have the means to convert an integer into binary, the next step will be to be able to use this binary representation and perform an addition with another binary representation, but that will be for the next post.

Here is your gift for making it this far in the post, until next time