Java code to convert between hex & binary strings

Question

I have two methods in my code which are using the majority of the CPU time that convert between binary and hex strings and the reverse. I use a static lookup map to convert the individual characters but it's still slow given the amount of data I'm working with.

public static String hexToBin(String s) 
{   
    StringBuilder binaryString = new StringBuilder();

    for(int i = 0; i < s.length(); i++)
    {
        // This string loop can be quite long sometimes > 3000 chars
        binaryString.append(binMap.get(s.charAt(i)));
    }

    return binaryString.toString();
}

public static String binToHex(String s)
{
    if (s.length() % 4 != 0)
    {
        s = Utils.leftPad4(s, (int)(4 * Math.ceil((double) s.length() / 4.0))); // Pad out any single bit values
    }

    StringBuilder hexString = new StringBuilder();
    StringBuilder chars = new StringBuilder();

    for (int i = 0; i < s.length(); i += 4)
    {
        chars.append(s.charAt(i));
        chars.append(s.charAt(i + 1));
        chars.append(s.charAt(i + 2));
        chars.append(s.charAt(i + 3));

        hexString.append(hexMap.get(chars.toString()));

        chars.delete(0, chars.length());
    }

    return hexString.toString();
}

/* The lookup tables */
private static Map<Character, String> binMap = new HashMap<>();
private static Map<String, Character> hexMap = new HashMap<>();

public Types()
{
    binMap.put('0', "0000");    binMap.put('1', "0001");    binMap.put('2', "0010");
    binMap.put('3', "0011");    binMap.put('4', "0100");    binMap.put('5', "0101");
    binMap.put('6', "0110");    binMap.put('7', "0111");    binMap.put('8', "1000");
    binMap.put('9', "1001");    binMap.put('A', "1010");    binMap.put('B', "1011");
    binMap.put('C', "1100");    binMap.put('D', "1101");    binMap.put('E', "1110");
    binMap.put('F', "1111");

    for (Character k : binMap.keySet())
    {
        hexMap.put(binMap.get(k), k);
    }
}

Answer 1

There are several things that hinder the performance of your code:

1. You are using a map to convert from hex digits to binary strings. However map lookups are slow, compared to simple array indexing or a switch statement . What you need to do, instead of using a map, just use a switch statement, when converting from hex to bin:

    switch (s.charAt(i))
    { 
      case '0':
        binaryString.append("0000");
        break;
      ...
      case 'F':
        binaryString.append("1111");
        break;
    }

However, this approach probably will not be as efficent when converting from bin to hex.

2. Because it is easy to calculate the length of a bin string from the length of a hex string, you can easily preallocate StringBuilder's with the calculated size. This will save you time, because the will be no memory reallocations.

3. If you code is not multithreaded, you could preallocate the StringBuilder's themselves and store them in some private fields of your class. This way you'd avoid spending time for unnecessary creation of the object, that would almost immediately be destroyed.

Answer 2

Ilkhd made good points about performance within the context of the task. I'll concentrate on a couple of generic issues.

Naming

public static String hexToBin(String s) 
public static String binToHex(String s)

The String parameter in the above method signatures is a hexadecimal string or binary string so they should be named hexString and binaryString, like is done with the local variables.

Utils.leftPad4(String, int)

The code for this mehtod is missing, but I assume it left-pads the String with the number of zeroes given in the int parameter. The 4 in the name seems unnecessary and confusing. The method doesn't seem to be very reusable either. It should be made into a generic left pad method: Utils.leftPad(String target, char padChar, int count). Although I'm fairly sure such a method already exists in one of the common utility libraries (Apache Commons, etc).

private static Map<Character, String> binMap = new HashMap<>();
private static Map<String, Character> hexMap = new HashMap<>();

If possible, the name of a map should describe the key and the value. These should thus be hexToBinMap and binToHexMap. They even managed to confuse me, since the first one does not map binary to anything. It maps hexadecimal characters to binary, so the naming was completely backwards. They have also been documented as lookup tables when they are actually lookup maps.

Performance

StringBuilder chars = new StringBuilder();
...
hexString.append(hexMap.get(chars.toString()));

This fills a StringBuilder with consecutive characters from a String and immediately converts it to another String. It should use String.substring(int startIndex, int endIndex) instead. This removes the unnecessary char array allocation done in StringBuilder.toString.

If you're concerned about performance, you should use an IDE, like Eclipse or Idea. They allows you to easily dig into the code in the JRE, like the StringBuilder.toString and examine yourself what it does. Knowing what the libraries you use is essential to performance optimization.

Error checking

binaryString.append(binMap.get(s.charAt(i)));

If the input string isn't a valid hexadecimal string, this will just append the string "null" to the binary string. There needs to be a check that the value returned from binMap.get(...) (or hexToBinMap as it should be) is not null. There is also no checking or documentation for upper vs lower case characters.

Finally

public static String hexToBin(String s) 
{   
    StringBuilder binaryString = new StringBuilder();

Whenever a piece of code declares a variable that is not intended to be changed, it should be declared final. This applies to method parameters, local variables and class members variables. This reduces the cognitive load of the maintainer as it removes the need to figure out if the variable is ever manipulated. The code above should thus become:

public static String hexToBin(final String s) 
{   
    final StringBuilder binaryString = new StringBuilder();

Answer 3

Ok, here my suggestions about your code, I noticed that you used s.length() in your code (two loops and leftpad function), better to store it in a variable and use this variable in your code rewriting loops and leftpad function.

int length = s.length()

Instead of using s.charAt(i) inside the loops, you can use the String method toCharArray() and memorize the String s into a char array, iterating over it inside the loops. You can rewrite the first loop in this way and the second one with some modifies to the code above avoid consecutive calls of the s charAt(i) method:

char[] arr =s.toCharArray();
int length = s.length();
for (int i = 0; i < length; ++i) {
    binaryString.append(binMap.get(arr[i]));
}

My concern is about the second parameter you are passing to it because you are doing a division between double numbers and after you cast the result to int, if you already know the result of s.length() % 4 you know that you have to pad your string with 4 - s.length() % 4 0 chars if I correctly interpreted the method you posted, so you would avoid the double division and the ceil method too.

Answer 4

public static String hexToBin(String s) 
{   
    StringBuilder binaryString = new StringBuilder();

You can improve efficiency here by telling the StringBuilder how long it will need to be.

public static final int BINARY_SIZE_OF_HEX = 4;

public static String hexToBin(String s) 
{   
    StringBuilder binaryString = new StringBuilder(BINARY_SIZE_OF_HEX * s.length());

Without this, it will allocate memory for a relatively small string, e.g. sixteen characters. Then it will reallocate memory for progressively longer strings. If the block of memory isn't long enough for expansion, it will copy the whole string to a new block of memory.

This way, it will allocate memory once and just enter the binary representation of the string thereafter.

This works because the translation between a hexadecimal representation and binary is straightforward. There are exactly four binary digits to every hexadecimal digit with the exception of the first. That may range from one to four digits. But your original version can be off by up to fifteen characters in length. Being off at most three is an improvement.

I also replaced the magic number 4 with a descriptively named constant.

        s = Utils.leftPad4(s, (int)(4 * Math.ceil((double) s.length() / 4.0))); // Pad out any single bit values

You could write this more simply as

    int distanceFromBoundary = s.length() % BINARY_SIZE_OF_HEX;
    if (distanceFromBoundary != 0)
    {
         // Pad out any single bit values
        s = Utils.leftPad4(s, s.length() + BINARY_SIZE_OF_HEX - distanceFromBoundary);

This saves a conversion to double, a floating point division, a ceiling operation, and a conversion to int at the cost of an integer addition, a subtraction, and a variable declaration. The variable will probably get compiled out into just a register use.

You also might consider if it would be better to handle the first digit separately rather than pad. Padding probably copies the whole string. But you don't need another copy of the string.