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^n1. Actual value of the number, given the
values of its digits, is then:
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:
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 lefthand
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 lefthand sum by
the base d, division remainder will be the value of lowest digit in the number
on the right:
Now that we have decided the value of lowest digit, we can completely remove it
from both sides of the equation:
Even more, both sides of the equation are now divisible by d after remainder
has been subtracted from them:
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 pencilandpaper 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 pencilandpaper 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
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 (236): ");
int numberBase = int.Parse(Console.ReadLine());
Console.Write("Enter new number base (236): ");
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 (236): 3
Enter new number base (236): 8
1002 (3) = 35 (8)
Enter number (empty to exit): 1002
Enter number base (236): 3
Enter new number base (236): 10
1002 (3) = 29 (10)
Enter number (empty to exit): 1002
Enter number base (236): 3
Enter new number base (236): 16
1002 (3) = 1D (16)
Enter number (empty to exit): 97ADSFKH32497GH2
Enter number base (236): 32
Enter new number base (236): 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 design patterns, writing unit and integration tests and applying methods to improve code design and longterm maintainability. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video courses at pluralsight.com (requires registration): Tactical Design Patterns in .NET: Managing Responsibilities Applying a design pattern to a realworld problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight into 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... 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
