StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The number <code>4946144450195624</code> fits 64 bits, its binary representation is:</p> <pre class="lang-none prettyprint-override"><code> 10001100100100111110111111110111101100011000010101000 </code></pre> <p>The program decodes a character for every 5-bits group, from right to left</p> <pre class="lang-none prettyprint-override"><code> 00100|01100|10010|01111|10111|11111|01111|01100|01100|00101|01000 d | l | r | o | w | | o | l | l | e | h </code></pre> <h1>5-bit codification</h1> <p>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).</p> <h1>Algorithm description</h1> <p>The <code>>>= 5</code> in the for-loop jumps from group to group, then the 5-bits group gets isolated ANDing the number with the mask <code>31₁₀ = 11111₂</code> in the sentence <code>l & 31</code></p> <p>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:</p> <pre class="lang-none prettyprint-override"><code> 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 </code></pre> <p>Here you can see that the ascii characters we want to map begin with the 7th and 6th bit set (<code>11xxxxx₂</code>) (except for space, which only has the 6th bit on), you could <code>OR</code> the 5-bit codification with <code>96</code> (<code>96₁₀ = 1100000₂</code>) and that should be enough to do the mapping, but that wouldn't work for space (darn space!)</p> <p>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 <code>64₁₀ = 1000000₂</code> (<code>l & 31 | 64</code>).</p> <p>So far the 5-bit group is of the form: <code>10xxxxx₂</code> (space would be <code>1011111₂ = 95₁₀</code>). If we can map space to <code>0</code> unaffecting other values, then we can turn the 6th bit on and that should be all. Here is what the <code>mod 95</code> part comes to play, space is <code>1011111₂ = 95₁₀</code>, using the mod operation <code>(l & 31 | 64) % 95)</code> only space goes back to <code>0</code>, and after this, the code turns the 6th bit on by adding <code>32₁₀ = 100000₂</code> to the previous result, <code>((l & 31 | 64) % 95) + 32)</code> transforming the 5-bit value into a valid ascii character</p> <pre class="lang-none prettyprint-override"><code>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 </code></pre> <p>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:</p> <pre class="lang-java prettyprint-override"><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); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload