Hex-to-octal converter

Question

The code converts hexadecimal into octal. The function is working, but it takes more than a second to process the input. How can I optimize this?

import java.util.Scanner;
public class BasicTranformSixteenToEight {

    public static void toBinaryTransform(int n, char[][] arry,
            String[] arryBinaryStr) {
        String[] arryOctalStr = new String[10];
        String str = "";
        StringBuilder octalStb = new StringBuilder();
        StringBuilder binaryStb = new StringBuilder();
        String[] arryOctalBinaryStr = { "000", "001", "010", "011", "100",
                "101", "110", "111" };
        for (int i = 0; i < n; i++) {
            arryBinaryStr[i] = "";
            for (int j = 0; j < arry[i].length; j++) { 
                switch (arry[i][j]) {
                case '0':
                    binaryStb.append("0000");
                    break;
                case '1':
                    binaryStb.append("0001");
                    break;
                case '2':
                    binaryStb.append("0010");
                    break;
                case '3':
                    binaryStb.append("0011");
                    break;
                case '4':
                    binaryStb.append("0100");
                    break;
                case '5':
                    binaryStb.append("0101");
                    break;
                case '6':
                    binaryStb.append("0110");
                    break;
                case '7':
                    binaryStb.append("0111");
                    break;
                case '8':
                    binaryStb.append("1000");
                    break;
                case '9':
                    binaryStb.append("1001");
                    break;
                case 'A':
                    binaryStb.append("1010");
                    break;
                case 'B':
                    binaryStb.append("1011");
                    break;
                case 'C':
                    binaryStb.append("1100");
                    break;
                case 'D':
                    binaryStb.append("1101");
                    break;
                case 'E':
                    binaryStb.append("1110");
                    break;
                case 'F':
                    binaryStb.append("1111");
                    break;
                default:
                    break;
                }
                arryBinaryStr[i] = binaryStb.toString();
            }
            if (arryBinaryStr[i].length() % 3 == 1) {  // Correct the Binary in order to convert it into Octal.
                arryBinaryStr[i] = "00" + arryBinaryStr[i];
            } else if (arryBinaryStr[i].length() % 3 == 2) {
                arryBinaryStr[i] = "0" + arryBinaryStr[i];
            }
            arryOctalStr[i] = "";
            for (int j = 0; j < arryBinaryStr[i].length() / 3; j++) { //convert Binary into Octal
                str = arryBinaryStr[i].substring(j * 3, j * 3 + 3);
                for (int k = 0; k <= 7; k++) {
                    if (str.equals(arryOctalBinaryStr[k])) {
                        octalStb.append(k);
                    }
                    arryOctalStr[i] = octalStb.toString();
                }
            }
            str = arryOctalStr[i].substring(0, 1);
            if (str.equals("0")) {  // Remove the first zero and print Octal.
                System.out.println(arryOctalStr[i].substring(1,
                        arryOctalStr[i].length()));
            } else {
                System.out.println(arryOctalStr[i]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] arry = new char[10][100000];
        String[] arryHexStr = new String[10];

        if (n >= 1 && n <= 10) {
            for (int i = 0; i < n; i++) {
                String number = sc.next();
                if (number.length() <= 100000) {
                    arry[i] = number.toCharArray();
                }
            }
            // binaryTransform(n,arry,arryHexStr);
            toBinaryTransform(n, arry, arryHexStr);
        }
    }
}

Answer 1

Profiling your code

You could use a profiler to get more insight into what takes up most of the time. Does the program spend much time on calculations, string operations, and/or something else? Are some of these taking longer and/or called more often than you expected?

The NetBeans IDE has the very nice VisualVM tool already built in, which makes it easy to give performance analysis a try. JProfiler and YourKit are popular profilers as well. See this list of Java performance analysis tools on Wikipedia, this blogpost on Java profilers, and this discussion on Stack Overflow for more information.

Processing numbers in six character blocks

To optimize your current code, you could use the fact that six characters from the hexadecimal string can be converted in eight characters for the octal string. If the hexadecimal string does not have a length that is a multitude of six, you can add zeroes in front of it to compensate for that; this will simplify the rest of your program.

Now you can process all the blocks of six hexadecimal characters and convert those into blocks of eight octal characters. The maximum value of a block "FFFFFF" fits in a Java Integer or int, which makes this conversion possible:

Integer.toOctalString(Integer.parseInt(hexadecimalBlockString, 16));

This converts from hexadecimal to decimal to octal, but without using strings. Finally, when a number has been converted to octal, you can strip the leading zeroes of if you want.

For example, this is a single block (the binary strings are only added for clarification and are not calculated during the actual conversion):

hexadecimal: "1    2    3    4    5    6"
binary:      "0001 0010 0011 0100 0101 0110"
------
binary:      "000 100 100 011 010 001 010 110"
octal:       "0   4   4   3   2   1   2   6"

Another approach: BigInteger

Another approach could be to use the BigInteger class:

private void convertHexadecimalToOctal() {
    List<BigInteger> numbers = new ArrayList<>();

    Scanner scanner = new Scanner(System.in);
    int numberCount = scanner.nextInt();

    if (numberCount >= 1 && numberCount <= 10) {
        for (int numberIndex = 0; numberIndex < numberCount; numberIndex++) {
            String hexadecimalNumber = scanner.next();
            if (hexadecimalNumber.length() <= 100000) {
                numbers.add(new BigInteger(hexadecimalNumber, 16));
            }
        }
    }

    for (BigInteger number : numbers) {
        System.out.println(number.toString(8));
    }
}

Some remarks

Some remarks about your code:

• arry can be an array (or a list) of String
• as JS1 already mentioned, arryHexStr is not a real parameter since it is not used to pass data to or from the toBinaryTransform method and could be a local variable
• I would break the toBinaryTransform method up into smaller methods and declare variables closer to where they are used

---

Some very minor remarks about your code:

• BasicTransformSixteenToEight instead of BasicTranformSixteenToEight?
• array instead of arry?
• hexToOctalTransform instead of toBinaryTransform?

Answer 2

• You present code that is essentially not documented/commented.

  Foremost, it is difficult to tell whether toBinaryTransform's main purpose is to produce a binary representation (which it assigns via one of its parameter, main never uses, neither title nor text mention) or to print an octal representation to System.out, which it also does and the title sort of singles out. (Or both, which might be an Awful Idea to begin with. If you implement a "multi result method" that strains resources, be sure to let the method know what will not be used.)

• Prefer functions to void methods.
• If you modify a parameter's value in a way observable outside a method, document that.

• Use the runtime's searches until you find cause and time to do better.

• Regarding performance:

  • Don't instantiate many/big elements without necessity
    String[] arryOctalStr = new String[10] doesn't get exposed or iterated, should have length n or arry.length, if any.
  • In main(), instantiate arry after checking n, with the length "needed": char[][] arry = new char[n][];
  • If you code a search and the first match is as good as the last, stop looking.

  • If you walk an array in steps of, e.g., 3, code it that way:

    binary = binSb.toString();
    //convert binary into octal
    for (int j = 0, n ; j < binary.length ; j = n) {
        n = j + 3;
        str = binary.substring(j, n);
        int k = Arrays.binarySearch(arryOctalBinaryStr, str);
        if (k < 0)
            wail(str + " is weird, or *gone*!");
        else
            octalStb.append(k);
    

  • Do not assign to "result variables" in each iteration of a loop if the only value needed is that after termination.

For micro-benchmarks and profiler runs, I coded a variant closer to the runtime library:

 /** convert an array of hex digits to a String of octal digits,
  *  avoiding <em>one</em> leading 0. */
    public static String hexToOctal(char[]hexDigits) {
        int h = hexDigits.length;
        if (h <= 0)
            return "";
        char[] octalDigits = new char[(h * 4 + 2) / 3];
        int o = octalDigits.length;
        while (3 <= h) { // byte value should do :-/
            int value = (char) hexValues[hexDigits[--h]];
            octalDigits[--o] = (char) ('0' + (value%7));
            value = (value >> 3) + doubleValues[hexDigits[--h]];
            octalDigits[--o] = (char) ('0' + (value%7));
            value = (value >> 3) + quadValues[hexDigits[--h]];
            octalDigits[--o] = (char) ('0' + (value%7));
            octalDigits[--o] = (char) ('0' + (value>>3));
        }
        int value = 0, conv[] = hexValues;
        switch (h) {
        case 2: value = hexValues[hexDigits[1]];
            octalDigits[2] = (char) ('0' + (value%7));
            conv = doubleValues;
        case 1: 
            value = (value >> 3) + conv[hexDigits[--h]];
            octalDigits[1] = (char) ('0' + (value%7));
            octalDigits[0] = (char) ('0' + (value>>3));
        }
        return '0' != octalDigits[0] ? new String(octalDigits)
            : new String(octalDigits, 1, octalDigits.length-1);
    }

 /** char for index */
    final static char[] digitChars
        = new char[9 - 0 + 1 + 'Z' - 'A' + 1];
 /** bit 1<<n set if a power of n<=6 (6*6<=digitChars.length) */
    final static int[] powerOf = new int[digitChars.length];
 /** exponent of base of lowest bit set in powerOf */
    final static int[] exponent = new int[digitChars.length];
    static final int
        digitValues[] = new int[Math.max('z', 'Z')+1],
        hexValues[]   = new int[Math.max('f', 'F')+1],
        doubleValues[]= new int[hexValues.length],
        quadValues[]  = new int[hexValues.length];
    static {
        try {
            for (char i = 0, c = '0' ; i <= 9 ; i++, c++) {
                digitValues[c] = i;
                digitChars[i] = c;
            }
            for (char i = 10, c = 'a' ; c <= 'z' ; i++, c++) {
                digitValues[Character.toLowerCase(c)] =
                    digitValues[Character.toUpperCase(c)] = i;
                digitChars[i] = c;
            }
            System.arraycopy(digitValues, 0,
                hexValues, 0, hexValues.length);
            for (int i = hexValues.length ; 0 <= --i ; ) {
                doubleValues[i] = 2 * hexValues[i];
                quadValues[i] = 4 * hexValues[i];
            }
        // iteration direction makes a difference with exponent:
        // going down, the entries at 4 and 16 end up with their
        // logarithm base 2 (2 and 4) instead of base 4 (1 and 2)
            for (int i = 6, b = 1 << i ; 1 < i ; i--, b >>= 1)
                for (int e=1, p=i ; p < powerOf.length ; p*=i) {
                    powerOf[p] |= b;
                    exponent[p] = e++;
                }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

Indications of work done in the same amount of time in my system, take with an appropriate amount of salt (baseToBase is much the same as hexToOctal, just for "all" conversions that can be done on groups of digits ("2,4,8,16->4,8,16,32"; 3->9,27; 5->25; 6->36; 9->27 and reverse)(and operating from the big end, probably slightly slower than backwards)):

toBinaryTransform  203
hexToOctal        3676
baseToBase        1730
parseLong&toString 981
BigInteger           6

BigInteger comes a surprise - almost all ticks in <init>(?!), would do about 10 times better with construction/parse as costly as toString.