Explain Please (TOH program)

[Script Coder]

I am looking into this iterative solution to the Towers of Hanoi problem. I specifically do not understand what is happening the logic in line 12. Any explanation is welcome.

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
   int n, x;
   printf( "How many disks? " );
   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;
}

[ResidentBiscuit]

It's bit manipulation. Now the logic, I'm not sure. I'm not too familiar with Towers of Hanoi. Just know what it is.

[Script Coder]

@Resident thank you, i will be sure to google. maybe i should rephrase my question (see above)

[ResidentBiscuit]

Ah sorry I couldn't be more help! I am curious now, so hopefully someone comes in and here explains the logic behind it. Ran the numbers on paper and it still seemed strange to me.

[Script Coder]

@resident you now know my pain about half an hour ago :)

[Kart]

How about we break it down into pieces and work it out?

(x&x-1)

break it into:

(x & (x-1))

which could mean & is the bitwise-AND operator?

Then break:

(x|x-1)+1

as
(x | (x-1))

which could mean | is the bitwise-OR operator.

Therefore
(x&x-1) is doing a bitwise AND with x and x-1.

and

(x|x-1) is doing a bitwise OR with x and x-1.

May be wrong though, but that's how i look at things sometimes

[ResidentBiscuit]

I think we both understand what is happening, more of a question of why.

[Script Coder]

Well i a have realized that x&x-1 is the same as x-1 when x is odd. I do not know if this helps, all I have so far