How does this iterative Tower of Hanoi work? C [du

Question

This question already has answers here:

Closed 9 years ago.

Possible Duplicate:
How does this work? Weird Towers of Hanoi Solution

While surfing Google, i found this interesting solution to Tower Of Hanoi which doesn't even use stack as data structure.

Can anybody explain me in brief, what is it actually doing?

Are this solution really acceptable?

Code

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int n, x;
   printf("How many disks?\n");
   scanf("%d", &n);
   printf("\n");
   for (x=1; x < (1 << n); x++)
      printf("move from tower %i to tower %i.\n",
         (x&x-1)%3, ((x|x-1)+1)%3);
return 0;
}

Update: What is the hard-coded number 3 doing in here?

Answer 1

It is one of the binary solutions to Tower of Hanoi, there is a detailed explanation of this algorithm on Wikipedia - read the "Binary solution" paragraph.

Answer 2

Might be easier to see in PSEUDOCODE:

GET NUMBER OF DISKS AS n
WHILE x BETWEEN 1 INCLUSIVE AND 1 LEFT-SHIFTED BY n BITS
    SUBTRACT 1 FROM n, DIVIDE BY 3 AND TAKE THE REMAINDER AS A
    OR x WITH x-1, ADD 1 TO THAT, DIVIDE BY 3 AND TAKE THE REMAINDER AS B
    PRINT "MOVE FROM TOWER " A " TO TOWER " B
    ADD 1 TO x

1 LEFT SHIFTED BY n BITS is basically 2 to the power of n, 16 in the case of 4 disks.

If you walk through this sequence manually, you should see the progression of movement of the disks. http://library.ust.hk/images/highlights/Tower_of_Hanoi_4.gif