Represent long in least amount of characters

Question

I need to represent both very large and small numbers in the shortest string possible. The numbers are unsigned. I have tried just straight Base64 encode, but for some smaller numbers, the encoded string is longer than just storing the number as a string. What would be the best way to most optimally store a very large or short number in the shortest string possible with it being URL safe?

Answer 1

I have tried just straight Base64 encode, but for some smaller numbers, the encoded string is longer than just storing the number as a string

Base64 encoding of binary byte data will make it longer, by about a third. It is not supposed to make it shorter, but to allow safe transport of binary data in formats that are not binary safe.

However, base 64 is more compact than decimal representation of a number (or of byte data), even if it is less compact than base 256 (the raw byte data). Encoding your numbers in base 64 directly will make them more compact than decimal. This will do it:

private static final String base64Chars =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";

static String encodeNumber(long x) {
    char[] buf = new char[11];
    int p = buf.length;
    do {
        buf[--p] = base64Chars.charAt((int)(x % 64));
        x /= 64;
    } while (x != 0);
    return new String(buf, p, buf.length - p);
}

static long decodeNumber(String s) {
    long x = 0;
    for (char c : s.toCharArray()) {
        int charValue = base64Chars.indexOf(c);
        if (charValue == -1) throw new NumberFormatException(s);
        x *= 64;
        x += charValue;
    }
    return x;
}

Using this encoding scheme, Long.MAX_VALUE will be the string H__________, which is 11 characters long, compared to its decimal representation 9223372036854775807 which is 19 characters long. Numbers up to about 16 million will fit in a mere 4 characters. That's about as short as you'll get it. (Technically there are two other characters which do not need to be encoded in URLs: . and ~. You can incorporate those to get base 66, which would be a smidgin shorter for some numbers, although that seems a bit pedantic.)

Answer 2

To extend on Stephen C's answer, here is a piece of code to convert to base 62 (but you can increase this by adding more characters to the digits String (just pick what characters are valid for you):

public static String toString(long n) {
   String digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
   int base = digits.length();
   String s = "";
   while (n > 0) {
      long d = n % base;
      s = digits.charAt(d) + s;
      n = n / base;
   }
   return s;
}

This will never result in the string representation being longer than the digit one.