3
$\begingroup$

Say we encode the string $BCA$ in the following way: \begin{align*}BCA &= 2 \times 26^2 + 3 \times 26^1 + 1 \times 26^0 \\ &= 1456 \end{align*} Is it possible to get back to the string $BCA$, given only the number $1456$?

2 Answers 2

3

Yes, it is possible as Mark has shown you one way to get the string digits from the least significant (that is getting $A$ first then $C$ and then $B$ finally).

But you have to be careful in using this method of encoding, because you are using base $26$, the number could be large if you are dealing with say strings of length $10$.

Another way to get back the strings is by calculating

$ \left \lfloor log_{26} 1432 \right \rfloor = 2 $

This tells you that the highest power of $26$ is $2$.

Start dividing by $26^2$ to get the most significant digit, i.e.

$ \left \lfloor \frac{1431}{26^2} \right \rfloor = 2 \tag{1}$

and from $(1)$ you know that most significant digit is $B$. The remaining number is

$ 1431 - 2 \times 26^2 = 1431 - 1352 = 79$

To find the next significant digit

$ \left \lfloor log_{26} 79 \right \rfloor = 1 $

and

$ 79 = \bf{3} \times 26 + \bf{1}$

Therefore you get the digits from the most significant to least as $B$, $C$ and $A$.

3

Yes. (But note that 1456 is not correct; $2\cdot26^2 + 3\cdot26 + 1 = 1431$, not $1456$.)

First, divide your number, 1431, by 26, giving quotient, 55, and a remainder, 1. The remainder of 1 means that the last letter is A.

Now divide the quotient 55 by 26, giving a quotient of 2 and a remainder of 3. The remainder, 3, says that the next-to-last letter is C.

Finally, divide the quotient 2 by 26, giving a quotient of 0 and a remainder of 2. This says that the next previous letter is B.

Now the quotient is 0, so we are done.

  • 0
    Decoding algorithms in general has to work both ways (left to right or right to left). Instead of re-inventing a new algorithm one could also use Base-32. (http://stackoverflow.com/questions/641361/base32-decoding)2012-05-10