Using two’s complement to store integers in memory

2’s complement of a binary number

Have you ever wonder how a machine’s stores numbers?, if your answer is no but you would like to know, then this post can help.

Let’s start by something simple, we know that a machine understands ones and zeros, right?, then if we want to store a number lets say 5 for instance, we’ll do it binary notation, right?

base 10: 5
base 2 : 101

Everything ok until this point. So we also know that machines uses bytes to store information, and that a byte is 8 bits long, so to make things simple we’ll assume that our number is stored using only 1 byte:

base 2: 00000101

As we know we can use positive and negative numbers in a computer, we use those numbers to make arithmetic operations for example, so this numbers (positives and negatives) corresponds to the signed value numbers a computer can handle, those numbers are stored in a special way to allow a computer identify if the number it’s reading is positive or negative, to identify this, we need a ‘bit’, usually the most significant one, if the bit is set to 1, the number should be negative, but if the ‘bit’ is set to 0, the number should be positive. To understand this better, I wrote a c program to read a byte’s bits, let’s take a look:

#include <stdio.h>
void print_bytes(char *ptr, int size)
{
  int i;
  printf("bytes: ");
  for (i = 0; i < size; i++)
    printf("%d ", ptr[i]);
  printf("\n");
}
void print_bits(char *ptr, int size)
{
  int i, j;
  int num;
  printf("bits : ");
  for (i = 0; i < size; i++)
  {
    num = (int) ptr[i];
    for (j = 7; j >= 0; j--)
      printf("%d", (num >> j) & 1);
    printf(" ");
  }
  printf("\n");
}
int main(void)
{
  int n;
  n = 5;
  printf("num: %d\n", n);
  print_bytes((char *)&n, sizeof(n));
  print_bits((char *)&n, sizeof(n));
  n = -5;
  printf("num: %d\n", n);
  print_bytes((char *)&n, sizeof(n));
  print_bits((char *)&n, sizeof(n));
  return (0);
}

This code looks inside the memory where a number is stored and prints the bytes and bits of each byte, let´s compile it and run it to see the output it gives:

$ gcc main.c 
$ ./a.out 
 num: 5
 bytes: 5 0 0 0 
 bits : 00000101 00000000 00000000 00000000 
 num: -5
 bytes: -5 -1 -1 -1 
 bits : 11111011 11111111 11111111 11111111

For simplicity we are just going to focus on 1 byte, in this case the first one. When the number is 5 we can see that the bits are the same we saw at the example at the beginnig, but when the number is negative, some weird number appears. Let’s find out why.

To store a negative number, computer’s use something known as 2’s complement, if we calculate the 2’s complement of 5 we’ll end up with the exact number we saw before, let’s separate the numbers to focus on the first’s byte of each one:

num: 5
bits : 00000101
num: -5
bits : 11111011

So let’s see what a 2’s complement is, following is a quote taken from wikipedia

Two’s complement is a mathematical operation on binary numbers, and is an example of a radix complement. It is used in computing as a method of signed number representation.

The two’s complement of an N-bit number is defined as its complement with respect to 2^N; the sum of a number and its two’s complement is 2^N. For instance, for the three-bit number 010, the two’s complement is 110, because 010 + 110 = 8 which is equal to 2^3. The two’s complement is calculated by inverting the bits and adding one.

So as wikipedia says, to calculate a 2’s complement, we must:

1. Invert all bits of the number (1’s complement)
2. Add one to the previous calculated number

We start with 5 and after this process, we should end with -5, let’s see the process:

num: 5
bits : 00000101
1.) Invert all bits: 
    bits : 11111010  -> 1’s complement
2.) Add one to this result
    11111010 + 1 = 11111011  -> 2’s complement
    num: -5

Wow!!, so this number is the same one we saw when printing the bits of -5, so this bits are gonna be stored in memory to represent a negative 5 using 2’s complement. As we saw, 2’s complement is a usefull way to store negative numbers.

That’s all for now , I hope this post helped you in some way, take care!.