How does this print "hello world"?

Question

I discovered this oddity:

for (long l = 4946144450195624l; l > 0; l >>= 5)
    System.out.print((char) (((l & 31 | 64) % 95) + 32));

Output:

hello world

How does this work?

Answer 1

The number 4946144450195624 fits 64 bits, its binary representation is:

 10001100100100111110111111110111101100011000010101000

The program decodes a character for every 5-bits group, from right to left

 00100|01100|10010|01111|10111|11111|01111|01100|01100|00101|01000
   d  |  l  |  r  |  o  |  w  |     |  o  |  l  |  l  |  e  |  h

5-bit codification

For 5 bits, it is posible to represent 2⁵ = 32 characters. English alphabet contains 26 letters, this leaves room for 32 - 26 = 6 symbols apart from letters. With this codification scheme you can have all 26 (one case) english letters and 6 symbols (being space among them).

Algorithm description

The >>= 5 in the for-loop jumps from group to group, then the 5-bits group gets isolated ANDing the number with the mask 31₁₀ = 11111₂ in the sentence l & 31

Now the code maps the 5-bit value to its corresponding 7-bit ascii character. This is the tricky part, check the binary representations for the lowercase alphabet letters in the following table:

  ascii   |     ascii     |    ascii     |    algorithm
character | decimal value | binary value | 5-bit codification 
--------------------------------------------------------------
  space   |       32      |   0100000    |      11111
    a     |       97      |   1100001    |      00001
    b     |       98      |   1100010    |      00010
    c     |       99      |   1100011    |      00011
    d     |      100      |   1100100    |      00100
    e     |      101      |   1100101    |      00101
    f     |      102      |   1100110    |      00110
    g     |      103      |   1100111    |      00111
    h     |      104      |   1101000    |      01000
    i     |      105      |   1101001    |      01001
    j     |      106      |   1101010    |      01010
    k     |      107      |   1101011    |      01011
    l     |      108      |   1101100    |      01100
    m     |      109      |   1101101    |      01101
    n     |      110      |   1101110    |      01110
    o     |      111      |   1101111    |      01111
    p     |      112      |   1110000    |      10000
    q     |      113      |   1110001    |      10001
    r     |      114      |   1110010    |      10010
    s     |      115      |   1110011    |      10011
    t     |      116      |   1110100    |      10100
    u     |      117      |   1110101    |      10101
    v     |      118      |   1110110    |      10110
    w     |      119      |   1110111    |      10111
    x     |      120      |   1111000    |      11000
    y     |      121      |   1111001    |      11001
    z     |      122      |   1111010    |      11010

Here you can see that the ascii characters we want to map begin with the 7th and 6th bit set (11xxxxx₂) (except for space, which only has the 6th bit on), you could OR the 5-bit codification with 96 (96₁₀ = 1100000₂) and that should be enough to do the mapping, but that wouldn't work for space (darn space!)

Now we know that special care has to be taken to process space at the same time as the other characters. To achieve this, the code turns the 7th bit on (but not the 6th) on the extracted 5-bit group with an OR 64 64₁₀ = 1000000₂ (l & 31 | 64).

So far the 5-bit group is of the form: 10xxxxx₂ (space would be 1011111₂ = 95₁₀). If we can map space to 0 unaffecting other values, then we can turn the 6th bit on and that should be all. Here is what the mod 95 part comes to play, space is 1011111₂ = 95₁₀, using the mod operation (l & 31 | 64) % 95) only space goes back to 0, and after this, the code turns the 6th bit on by adding 32₁₀ = 100000₂ to the previous result, ((l & 31 | 64) % 95) + 32) transforming the 5-bit value into a valid ascii character

isolates 5 bits --+          +---- takes 'space' (and only 'space') back to 0
                  |          |
                  v          v
               (l & 31 | 64) % 95) + 32
                       ^           ^ 
       turns the       |           |
      7th bit on ------+           +--- turns the 6th bit on

The following code does the inverse process, given a lowercase string (max 12 chars), returns the 64 bit long value that could be used with the OP's code:

public class D {
    public static void main(String... args) {
        String v = "hello test";
        int len = Math.min(12, v.length());
        long res = 0L;
        for (int i = 0; i < len; i++) {
            long c = (long) v.charAt(i) & 31;
            res |= ((((31 - c) / 31) * 31) | c) << 5 * i;
        }
        System.out.println(res);
    }
}