Positional notation#Base conversion

The transformation of the representation of a number in a place value system to another, for example from the binary or dual system to the everyday common decimal system used in digital technology, is called the number of base exchange. For this process, suitable algorithms are needed. The change takes place from a source system through to the target system.

Motivation

Among the number of systems in addition to our usual decimal system also value systems with other cardinal numbers are used today.

So figures in information technology are normally presented in the dual system, as it is well suited for processing by electronic circuits. When the input and output on the other hand provides you prefer the numbers in a system that is worth more readable for humans. In addition to the decimal system and the octal and the hexadecimal system are often used for this purpose, since both are particularly easy to be transformed into the dual system.

In other cultures, and in earlier times came for various reasons, other value systems are used, which is of physical quantities, is still visible, particularly in the classification of certain units.

This often results in the need to transform the representation of a number from one place value system to another. Below is the place value system, to be transformed by the, called the source system and the value system in which is transformed as the target system.

Conversion for simple special cases

If the base number n of the target system is a positive integer power of the base number m of the source system (ie n = m for any positive integer i), then the conversion process is particularly simple. In this case, can be groups namely from each i digits of a number in the source system convert directly into a number of the target system. Conversely, it is of course equally possible to transform a digit of a number of the source system into several digits of the target system when the base number of the source system is a positive integer power of the base number of the target system. Since the size of the groups of digits in these cases usually moves in a manageable range, such conversions can be easily performed with the help of tables. The transformation between dual and octal is possible for example with the following table:

Thus, the conversion of the binary number 10011101 into octal yields (i = 3):

The transformation between dual and hexadecimal can be reached via the following table:

This method also works for other cases. It is sufficient that the base numbers m and n are powers of a common base B, that is, it is m = n = bi and bj, where i and j are natural numbers. In the naive case, first with the method just shown in the base number b converted to switch then n in the representation of the basic number. For example, as the conversion from octal (m = 8 = 23) in hexadecimal (n = 16 = 24) via the detour of the dual system ( b = 2 ) is possible.

It is always low, the base number b to normalize in such a way that one of the greatest common divisor of i and j. If this is not the case, can be selected instead of the base number b bz and instead of i and j are the numbers i / z and y / z, where z = gcd (i, j).

Instead of the naive method indirectly via the base number b but can also be converted directly between such value systems. Here, then y / z digits of the number in the notation for the cardinal number m are converted into i / z digits of the number in the notation for the cardinal number n, where again z = gcd (i, j ) holds. Such a table is easy to create with the naive method. The conversion between the place value system to the base 4 and the octal system is for example possible with the following table:

Conversion in the general case

There are essentially two ways to represent numbers in a place value system in the representation of numbers to result in a different value system. Which one is used depends on the prevailing conditions.

First, it should be noted that a string to be transformed into another. In programming languages, strings are usually represented by variables of type String. On such types of typical string operations can be performed. Only those operations essentially:

• IsEmpty ( s ), which checks whether the string s is empty, so has the length zero,
• CatFirst (C, S ) connected to the beginning of the string s and the character c is
• CutFirst ( s ) that cuts the first character of the string s, and returns,

Needed.

The algorithms for the change of basis be simplified if it is agreed that an empty string with 0 's identify. Would in real world applications, the string can be used for "0". This specific case but can easily be additionally intercept.

At least in a system must on the strings certain basic arithmetic operations can be performed. Depending on which system will find the required basic arithmetic operations are available, one of the alternatives is selected. The algorithms for basic arithmetic operations are not trivial. Known from the school algorithms for the decimal example, can be adapted for other value systems (see Arithmetic in value systems). More efficient algorithms for multiplication, however, would be, for example, the Karatsuba algorithm, the Toom - Cook algorithm or the Schönhage - Strassen algorithm.

Option 1: basic arithmetic in the source system

If the Division (Operator / ) with residual ( " modulo " operator %) in the source system, so the representation of a number in the source system in the representation of the same number in the target system can be transformed as follows:

First, the representation is (the string) (the empty string ) is set in the target system to zero. As long as the string in the source system from zero (ie, not the empty string ) is different, a sequence is repeated instructions that initially forms the rest of the string in the source system when divided by the base value of the target system. This number is then translated directly from a table in the corresponding digit of the target system and those preceded by a most significant digit of the representation of the target system. Then the string is divided in the source system through the base number of the target system. The following pseudo code illustrates this.

Target system function convert ( source system source ) {      Target target = "";      while (! quelle.isEmpty ) {         target = catFirst ( convertSimple (source zbasis % ), target)         source = source / zbasis;      }      return target; } The variable source is of type source system and the target variable of type target system. With zbasis a constant of type source system is designated that contains the base number of the target system.

The operation convertSimple ( s ) assigns a variable of type source system in the range of 0 to b-1 directly to the relevant point in the target system. Here, b is the base value of the target system. This is for example easily possible on a table.

Option 2: basic arithmetic operations in the target system

Standing the basic arithmetic multiplication ( * operator ) and addition ( operator ) in the target system, so the representation of a number in the source system can be transformed into the representation of the same number in the target system as follows.

Also here the representation ( ie the string ) in the target system to zero is first (ie the empty string ) is set. As long as the string in the source system from zero (ie, not the empty string ) is different is a sequence of instructions carried out, the first the first character (ie the most significant digit ) of the representation separates the source system and the value of directly using a table in a number target system translated. Subsequently, this number is added to the digit sequence in the target system after it has been multiplied by the base number of the source system. The following pseudo code illustrates this.

Are the basic arithmetic operations in the target system is available, the following algorithm leads to the goal:

Target system function convert ( source system source ) {      Target target = "";      while (! quelle.isEmpty ())         target = target * Qbasis convertSimple ( cutFirst (source ) );      return target; } The variable source is again of the type source system and the target variable of type target system. With Qbasis a constant of type target system is designated that contains the base number of the source system.

The operation convertSimple ( s ) assigns a number from the source system to a number in the target system. This is for example easily possible on a table.