“Towers of Hanoi”: Bitstring solutions

Java implementation by Apostolos Syropoulos

The solution by Glenn C. Rhoads
is based on treating the current move number as a bit string and uses
bit operations to extract the information in a surprisingly short,
efficient, and mysterious manner. The solution assumes that poles are
numbered from 0 to 2 and the initial pole is pole number 0. Now, if the
current move number is even then the destination pole is pole number 1,
else it is pole number 2. Suppose that the variable `x` holds the
current move number, then the destination pole is computed by the expression

and the pole of departute by the expression

Back to main page

Get the source code

The soloution by Adam Moorhouse is based on ideas similar to the above solution. The author enumerates the poles from 1 to 3. Here is an explanation of the solution in the authors own words (the original code is in C++, but here we present the Java equivalent):

static void hanoi(int height)
{
final double log2 = Math.log(2);
for( int move = 1; move < (1 << height) ; move++)
{
// The piece moved is the most significant bit changed
// when we go from

The command `moveDisk( (char)(from+65), (char)(to+65));` is common
to both solutions and it is a simple trick to print A instead of 0, B instead
of 1, and C instead of 2.