Base Conversion

This post will explore an approach to converting a number between different bases, e.g. decimal, hexadecimal, octal, and everything in between. A concrete example might look something like this - (12)10 = (C)16 = (10000)2 with the subscript denoting the base. The general idea is to first convert the number in the given base to decimal, and the second step would be to convert from decimal to the desired base. Suppose we want to convert (913)7 to base 13.

# let x = 0
# 9 : 0 * 7 + 9 = 9
# 1 : 9 * 7 + 1 = 64
# 3 : 64 * 7 + 3 = 451

# x = 451 // This is 913 in base 10

# 451 % 13 = 9   451 / 13 = 34 // the new value of x
#  34 % 13 = 8    34 / 13 = 2  // the new value of x
#   2 % 13 = 2     2 / 13 = 0  // the new value of x
# 289 // this is 451 in base 13

Approach

As shown in the illustration, the first step is to convert the given number in the given base to its base 10 counterpart. This is done by iterating through the digits of the given number, starting with the most significant digit, and multiplying the aggregate value by the given base and then adding the digit to the aggregate. Repeat this for the length of the given number. The result will be a base 10 representation of the given number. The key concept to note here is that multiplying by a base effectively moves the digits to the left. This is more obvious with base 10 where multiplying the number 3 by 10 results in 30, which shifts the number 3 to the left by 1.

We can skip to the second step if the given number is already in base 10. This step takes advantage of the property of modulo and the divide operators. The modulo helps pick out the least significant digit while the divide operator reduce a number by the magnitude of the base. This is repeated until the number becomes zero.

Implementation

public static String convert(String givenNumber, int b1, int b2) {
    int x = 0;
    for (int i = 0; i < givenNumber.length(); i++) {
        char c = givenNumber.charAt(i);
        x = (x * b1 + (Character.isDigit(c)
            ? c - '0'
            : c - 'A' + 10));
    }

    StringBuilder sb = new StringBuilder();
    while (x > 0) {
        int r = x % b2;
        char c = (char) (r >= 10
            ? 'A' + r - 10
            : '0' + r);
        sb.append(c);
        x /= b2;
    }

    return sb.reverse().toString();
}

This article is my 38th oldest. It is 464 words long, and it’s got 0 comments for now.