Number System is a consistent way of expressing a number. It consists of three parts:

1. The Symbol – It can be digits, letters or any other symbol.
2. The Position – The position of symbols determine their weight.
3. The Base – The total number of different symbols supported.

Number system is often named after the size of its base. For example, the “Decimal Number System”, with symbols $(0,1,2,3,4,5,6,7,8,9)$. Since there are $10$ different symbols, the base is $10$.

The Decimal Number System is the standard number system that we use in our everyday life. We will use this system as our reference for other systems. Since we will be looking into lots of different number systems in this article, from now on I will write numbers in decimal number system as $(number)_{10}$. In general, $(x)_{y}$ means $x$ is a number with base $y$.

How Number System Works

As mentioned before, Number System consists of three parts.

Symbols in Number System

In decimal number system, the first few numbers we encounter are $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$. Then we run out of symbols. We add a new position at the front of the number and start placing number in those to continue counting: $8, 9, 10, 11, 12, 13…$

The same concept is used with number system of different base. For example, let us consider a number system with 3 different symbols: $(0,1,2)$. The first few numbers in this system are: $0,1,2$. Once we run out of symbols we introduce new positions and get: $10,11,12,20,21,22,100,101,102,110$.

Position of Symbol

In a number, the position of symbols is $0$ indexed and ranked from right to left. For example, the number $54711$ will have the following index for its positions:

The last digit of the number has position index $0$. The index increases as we go left.

The position in a number represents the weight of the symbol in that position. A symbol in a higher position values more than one in a lower position. For example in the decimal number system, we know that $2 > 1$. But if we consider $1$ in a higher position then $100 > 20$. How is the weight of each position calculated exactly? The answer is in next section.

Base of Number System

The “Base” of number system determine the weight of each position.

For example, $(1234)_{10} = 1000 + 200 + 30 + 4 = 1 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 4 \times 10^0$.

Here the weight of the symbol in $0_{th}$ position is $10^0$, $1_{st}$ position is $10^1$, $2_{nd}$ position is $10^2$ and $3_{rd}$ position is $10^3$. As the position increases, the weight of position increases by $10$. A symbol in $n_{th}$ position carries $10^n$ weight.

But this is true only for the decimal number system. The weight is a power of $10$ for decimal system cause it has a base of $10$. A number system with base $B$ will have weight $B^n$ for $n_{th}$ position.

Binary Number System

Binary Number System is a Number System with Base $2$. It has only two symbols: $(0,1)$. This number system is used by computers to store information. As programmers, we will frequently work with binary numbers, so we need to understand this system properly.

Since we are used to the Decimal Number System, it might be awkward to work with the binary system at first. But we will get used to it pretty soon.

Here are the first few numbers in Binary System.

Binary to Decimal

We will first look into how we can convert a number from binary to the decimal system.

Suppose we want to find the value of $(11001)_2$ in decimal. How do we find it? Remember that we learned that a symbol in $n_{th}$ position has $Base^n$ weight. What is the base in the binary system? $2$. So this number can be written as:

$(11001)_2 = 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 16 + 8 + 0 + 0 + 1 = (25)_{10}$

Decimal to Binary

Solve $(19)_{10} = (?)_2$. We need to convert $19$ to binary.

A number $x$ in binary system is of form: $x = s_n2^n +…+s_32^3+s_22^2+s_12^1+s_02^0$, where $s_i$ is the symbol in $i_{th}$ position. What happens when we find $x \% 2$? Since all position except for $0_{th}$ position is multiple of $2$, $x \% 2 = s_0$.

That is, finding the value of $x \% 2$ gives us the last digit of $x$ in the binary system.

Okay, we got the digit in $0_{th}$ position, how do we find the rest? In order to find the digit in next position, we divide $x$ by $2$. What happens if we divide $x$ by $2$?

$\frac{x}{2} = s_n2^{n-1} +…+s_32^2+s_22^1+s_12^0+\frac{s_0}{2}$
$\therefore \lfloor \frac{x}{2} \rfloor = s_n2^{n-1} +…+s_32^2+s_22^1+s_12^0$

That is, when we divide $x$ by $2$, the last digit of $x$ disappears and all digits of $x$ shifts one place to right. For example, if $x$ is $(11011)_2$ then $\frac{x}{2}$ is $(1101)_2$.

In C++, we can easily perform this floor division by simply performing integer division. Once we divide it, we then find the value of $\lfloor \frac{x}{2} \rfloor \% 2$. By repeating this until $x$ becomes $0$, we can find all digits.

Let us try to solve the problem $(19)_{10} = (?)_2$.

$x=19: x \% 2 = 1$
$x = \lfloor \frac{19}{2} \rfloor = 9: x \% 2 = 1$
$x = \lfloor \frac{9}{2} \rfloor = 4: x \% 2 = 0$
$x = \lfloor \frac{4}{2} \rfloor = 2: x \% 2 = 0$
$x = \lfloor \frac{2}{2} \rfloor = 1: x \% 2 = 1$
$x = \lfloor \frac{1}{2} \rfloor = 0: \text{end}$
$\therefore (19)_{10} = (10011)_2$

Hexadecimal Number System

Hexadecimal Number System is a Number System with Base $16$. It has 16 symbols, $(0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)$. We already saw Decimal to Binary conversion and vice versa. Looking into Decimal-Hexadecimal conversion and vice verse will help us understand the base conversions better.

Here are the first few numbers in Hexadecimal System.

In hexadecimal system, $(A,B,C,D,E,F)$ corresponds to the decimal value $(10,11,12,13,14,15)$.

Hexadecimal to Decimal

Suppose we want to find the value of $(1A3F2B)_{16}$ in decimal. Using the same logic as Binary to Decimal conversion, we can say that:

$(1A3F2B)_{16} = 1 \times 16^5 + A \times 16^4 + 3 \times 16^3 + F \times 16^2 + 2 \times 16^1 + B \times 16^0$
$(1A3F2B)_{16} = 1 \times 16^5 + (10) \times 16^4 + 3 \times 16^3 + (15) \times 16^2 + 2 \times 16^1 + (11) \times 16^0$
$(1A3F2B)_{16} = 1048576 + 10 \times 65536 + 3 \times 4096 + 15 \times 256 + 2 \times 16 + 11 \times 1$
$(1A3F2B)_{16} = 1048576 + 655360 + 12288 + 3840 + 32 + 11$
$(1A3F2B)_{16} = (1720107)_{10}$

Decimal to Hexadecimal

Solve $(123456789)_{10} = (?)_{16}$.

A number $x$ in hexadecimal system is of form: $x = s_n16^n +…+s_316^3+s_216^2+s_116^1+s_016^0$, where $s_i$ is the symbol in $i_{th}$ position.

Just like Binary System, finding the value of $x % 16$ gives us the last digit of $x$ in hexadecimal system. To find the rest, we divide it by $16$ and find the last digit again.

$\frac{x}{16} = s_n16^{n-1} +…+s_316^2+s_216^1+s_116^0+\frac{s_0}{16}$
$\therefore \lfloor \frac{x}{16} \rfloor = s_n16^{n-1} +…+s_316^2+s_216^1+s_116^0$

Let us try to solve the problem $(123456789)_{10} = (?)_{16}$.

$x=123456789: x \% 16 = 5$
$x = \lfloor \frac{123456789}{16} \rfloor = 7716049: x \% 16 = 1$
$x = \lfloor \frac{7716049}{16} \rfloor = 482253: x \% 16 = 13$
$x = \lfloor \frac{482253}{16} \rfloor = 30140: x \% 16 = 12$
$x = \lfloor \frac{30140}{16} \rfloor = 1883: x \% 16 = 11$
$x = \lfloor \frac{1883}{16} \rfloor = 117: x \% 16 = 5$
$x = \lfloor \frac{117}{16} \rfloor = 7: x \% 16 = 7$
$x = \lfloor \frac{7}{16} \rfloor = 0: \text{end}$
$\therefore (123456789)_{10} = (75BCD15){16}$

Notice how we replaced the remainder value $11,12,13$ with $B,C,D$. Since the value $(10,11,12,13,14,15)$ represents $(A,B,C,D,E,F)$ in hexadecimal, we use the proper symbols in the number.

Number System with Base $B$

We saw how to work with Binary and Hexadecimal number system. We will now generalize the approach.

Suppose there is number $x$ in base$B$, then $x = d_nd_{n-1}..d_3d_2d_1d_0$, where $0 \leq d_i < B$.

Base to Decimal

The number $x$ in decimal will be $d_n \times B^n + d_{n-1} \times B^{n-1} + … + d_1 \times B^1 + d_0 \times B^0$.

Here is a code that can convert a number in base $B$ into decimal.

 
int baseToDecimal ( string x, int base ) {
    int res = 0;
    int len = x.length();

    int coef = 1; // initially base^0
    for ( int i = len - 1; i >= 0; i-- ) { // Start from reverse
        res += (x[i]-'0') * coef;
        coef *= base; // increase power of base
    }
    return res;
}

The number $x$ here is a string. That is because $x$ can have symbols that are not digits, for example, $(AB12)_{16}$. We find out the length of the number in line $3$. Then we iterate over the number from last digit to the first digit. We start from back where the coefficient of the digit is $base^0 = 1$. Every time we change position, we multiply the coefficient by $base$. This ensures we multiply $d_n$ with $base^n$.

If we want we can convert the number to decimal from the front of the number, that is from first digit to last digit.

Suppose we want to make the number $d_1d_2d_3$ in base $B$. We can start with the digit $d_1$ only. Then we can move it to left of its position by multiply it by $B$, $d_1B^0 \times B = d_1B^1$. Then if we add $d_2$ with it, it becomes $d_1B^1 + d_2 = d_1d_2$. We multiply it by $B$ again and then add $d_3$. It finally becomes $d_1d_2d_3$.

For example, $(123)_{10} = (1 \times 10 + 2 ) \times 10 + 3$.

Using this idea, we can write the following code:

 
int baseToDecimalAlternate ( string x, int base ) {
    int res = 0;
    int len = x.length();

    for ( int i = 0; i < len; i++ ) {
        res = ( res * base ) + (x[i]-'0');
    }
    return res;
}

Here we iterate the number $x$ from $0$ to $len-1$ in line $5$. Line $6$ is what I explained above.

The alternate method is shorter and sometimes makes a problem easier to solve. Knowing both method helps us approach problems from different directions.

Decimal To Base

$x \% B$ will give us the last digit of $x$ in base $B$. We can get the remaining digits by repeatedly dividing $x$ by $B$ and taking its last digit until $x$ becomes 0.

$x = x: d_0 = x \% B$
$x = \lfloor \frac{x}{B} \rfloor: d_1 = x \% B$
$...$

Here is how we will do it in code:

// A list of symbol. Depending on base and number system, this list can be different.
char symbol[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
string decimalToBase ( int x, int base ) {
    string res = "";

    while ( x ) {
        int r = x % base; // Find the last digit
        res = res + symbol[r]; // Change the integer value to symbol and append to res
        x /= base; // Remove the last digit
    }
    if ( res == "" ) res = symbol[0]; // If res is empty, that means x is 0.
    reverse ( res.begin(), res.end()); // We found the digits in reverse order.
    return res;
}

In line $2$ we have a symbol list. Since we are converting to a different base, it will have symbols for each value from $0$ to $B-1$. We keep on finding the last digit of $x$ until it becomes $0$ in the loop at line $6$. The last digit is found in line $7$. We append it to the result in line $8$ and we divide $x$ by $B$ in line $9$. In line $11$ we check if $res$ is empty. If it is then $x$ was $0$ from the beginning, so we append $0$ to $res$. In line $12$ we reverse the whole string $res$ since we generated the digits in reverse order, i.e, from last digit to the first digit.

Resource

1. tibasicdev.wikidot - Binary, Hexadecimal and Octal number system

• Category: CPPS, Number Theory