http://www.codinghelmet.com/  

Wear a helmet. Even when coding.

exercises > converting-number-bases

Exercise #13: Converting Number Bases
by Zoran Horvat @zoranh75

Problem Statement

Given a string representing a number, base in which the number is written and new base to which number should be converted, write a function which produces a string representing the same number in new base. Digits higher than 9 should be represented by capital letters A, B, ..., Z. Together with decimal digits 0 to 9, this makes total of 36 digits that can be represented. Hence, both bases will be numbers between 2 and 36, inclusive.

Example: For number 1002 with base 3 and new base 8 (octal number) output value should be 35. Same number in new base 10 would produce output 29, and in new base 16 (hexadecimal number) it would produce output 1D.

Problem Analysis

This exercise deals with numbers written in positional system. This means that each position is associated with specific "weight", or a multiplier applied to the digit at that position. Take decimal numeric system as an example. Weights associated with positions are one, for lowest digit, ten, for the following digit, a hundred, a thousand, and so on.

In general case, when number is written in positional system with base b with total of n digits, weights of positions would grow exponentially with position number: b^0, b^1, b^2, ... , b^n-1. Actual value of the number, given the values of its digits, is then:

Positional number value

Now we can begin solving the problem. We are given a number in base b in form of a stream of digits. The task is to entail digits of another number in base d, so that values of two numbers are equal:

Positional numbers equation

There are some oddities to note about this formula. First, bases of two numbers are different. Second thing is the consequence: number of digits differs in two numbers, in general case. Even more, although number of digits in the left-hand number (n) is known in advance, the length of the number on the right (m) is unknown. It could be deduced from n and number bases but, as will soon become obvious, we don't really need to know m.

It would be quite difficult to guess all the digits in the second number at once, given the number value (sum on the left side of the equation) and the target base d. This conclusion leads to the idea of entailing target number digits in some sort of an iterative process. One possibility is to build on the fact that lowest digit in the target number is solely determined by the overall number value. It is not affected by higher digits in any way (this is the core quality of all positional number systems). If we divide the left-hand sum by the base d, division remainder will be the value of lowest digit in the number on the right:

Least significant digit

Now that we have decided the value of lowest digit, we can completely remove it from both sides of the equation:

Positional number without least significant digit

Even more, both sides of the equation are now divisible by d after remainder has been subtracted from them:

Reduced positional number

Net result of this transformation is that now we have got a completely new number in base b on the left side. At the same time, number on the right side in base d has all digits left intact, with only the lowest digit missing - the lowest digit has been eliminated from the equation. What used to be the second lowest digit in the target number has now become the least significant digit in the new target number.

Way forward from this point is quite simple. Just repeat the process once more to extract the next lowest digit in the target number. And again, repeat the process to calculate the next digit and so on. Digits are deduced one at a time, until all m digits are calculated. The only difficulty is that m is not known. So we need a stopping condition.

If we observe the process described above, we will notice that the number on the left side of the equation is reduced in every step. This comes from dividing that number with base d. As the process continues, we can expect that at some point the whole number is going to become equal to zero. Th would be the point in which we stop looking for more digits on the right. Should we continue, all further digits would be zero - leading zeros, in fact - and they are not needed.

So the stopping criterion is to look when the source number drops to zero. This comes with a trap: the source number might already be zero at the beginning, even before we have extracted the first digit for the resulting number in base d. In that case, the resulting number should also be set to zero and the whole calculation skipped entirely.

The core function which converts number bases is now fairly simple, although dependant on a couple of helper functions:

function ConvertNumber(number, b, d)
begin
    newNumber = ""
    while number <> "0"
        begin
            number = Divide(number, b, d, out remainder)
            newDigit = ValueToDigit(remainder)
            newNumber = Concatenate(newDigit, newNumber)
        end
    if newNumber ="" then
        newNumber = "0"
end

Most important helper function used is called Divide. It receives a number, its base and a divisor. On output, this function returns result of the division, which is a number in base which was specified as an argument. In addition, the function returns division remainder through an output parameter. Here is the pseudocode of this function:

function Divide(number, base, divisor, out remainder)
begin
    remainder = 0
    result = ""
    for i = 0 to Length(number) - 1
        begin
            digitValue = DigitToValue(number[i])
            remainder = base * remainder + digitValue
            newDigitValue = remainder / divisor -- integer division
            remainder = remainder mod divisor
            if newDigitValue > 0 OR result <> "" then
                newDigit = ValueToDigit(newDigitValue)
                result = Concatenate(result, newDigit)
        end
    if result = "" then
        result = "0"
    return result
end

There are a few points to mention in this function. First of all, implementation is based on simple pencil-and-paper algorithm. But the catch is that division is performed in specified base, rather than in decimal number system. As a consequence, we only have current digit and current remainder converted to integers at any given time. This is simply because division and modulo operations in programming languages are defined for integers, rather than for numbers with arbitrary base.

Nevertheless, this pencil-and-paper process produces one output digit in every step, and these digits are appended to the resulting number from most significant position towards less significant ones. And again, there is a catch. If digit produced on the output is zero and resulting number is empty (this is the first digit), then the digit is dropped. It would be a leading zero anyway, and it serves no purpose in the number apart from needlessly growing it in length. But then, there is another catch: if no digits are appended to the result by the end of the loop, then one zero is still passed to it (this is the result of the final if statement in the function). This step resolves the situation where all digits in the result are leading zeros, meaning that the whole output number is zero.

Implementation

Below is the complete implementation of console application in C# which converts number bases.

using System;

namespace ChangingBases
{

    public class OperationResult
    {

        static int DigitToValue(char digit)
        {

            int value = 0;

            if (digit >= '0' && digit <= '9')
                value = digit - '0';
            else // digit is between 'A' and 'Z'
                value = digit - 'A' + 10;

            return value;

        }

        static char ValueToDigit(int value)
        {

            char digit = '\0';

            if (value < 10)
                digit = (char)('0' + value);
            else
                digit = (char)('A' + (value - 10));

            return digit;

        }

        static string Divide(string number, int numberBase, int divisor,
                             out int remainder)
        {

            remainder = 0;
            string result = string.Empty;

            for (int i = 0; i < number.Length ; i++)
            {

                int digitValue = DigitToValue(number[i]);
                remainder = numberBase * remainder + digitValue;
                int newDigitValue = remainder  divisor;
                remainder = remainder % divisor;

                if (newDigitValue > 0 || result != string.Empty)
                {
                    char newDigit = ValueToDigit(newDigitValue);
                    result = result + newDigit;
                }

            }

            if (result == string.Empty)
                result = "0";

            return result;

        }

        static string ConvertNumber(string number, int numberBase,
                                    int newBase)
        {

            string newNumber = string.Empty;

            while (number != "0")
            {
                int reminder = 0;
                number = Divide(number, numberBase, newBase, out reminder);
                char newDigit = ValueToDigit(reminder);
                newNumber = newDigit + newNumber;
            }

            if (newNumber == string.Empty)
                newNumber = "0";

            return newNumber;

        }

        static void Main(string[] args)
        {

            Console.Write("Enter number (empty to exit): ");
            string number = Console.ReadLine();

            while (!string.IsNullOrEmpty(number))
            {

                Console.Write("    Enter number base (2-36): ");
                int numberBase = int.Parse(Console.ReadLine());

                Console.Write("Enter new number base (2-36): ");
                int newBase = int.Parse(Console.ReadLine());

                string newNumber = ConvertNumber(number, numberBase, newBase);

                Console.WriteLine("{0} ({1}) = {2} ({3})",
                                  number, numberBase, newNumber, newBase);

                Console.Write("Enter number (empty to exit): ");
                number = Console.ReadLine();

            }

        }

    }
}

Demonstration

When application is run, it produces output like this:

Enter number (empty to exit): 1002
    Enter number base (2-36): 3
Enter new number base (2-36): 8
1002 (3) = 35 (8)
Enter number (empty to exit): 1002
    Enter number base (2-36): 3
Enter new number base (2-36): 10
1002 (3) = 29 (10)
Enter number (empty to exit): 1002
    Enter number base (2-36): 3
Enter new number base (2-36): 16
1002 (3) = 1D (16)
Enter number (empty to exit): 97ADSFKH32497GH2
    Enter number base (2-36): 32
Enter new number base (2-36): 10
97ADSFKH32497GH2 (32) = 348659477389970058232354 (10)
Enter number (empty to exit):

See also:

Published: Nov 3, 2013

ZORAN HORVAT

Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on object-oriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and long-term maintainability.

Follow him on Twitter @zoranh75 to receive updates and links to new articles.

Watch Zoran's video courses at pluralsight.com (requires registration):

Making Your C# Code More Object-Oriented

This course will help leverage your conceptual understanding to produce proper object-oriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More...

Advanced Defensive Programming Techniques

This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More...

Tactical Design Patterns in .NET: Creating Objects

This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More...

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straight-forward as literature implicitly tells us. It is a more engaged process. This course gives an insight to tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More...

Tactical Design Patterns in .NET: Control Flow

Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More...

Writing Highly Maintainable Unit Tests

This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. More...

Improving Testability Through Design

This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More...

Share this article

webmasters