From Tower of Hanoi to Counting Bits (2011)

Re:From Tower of Hanoi to Counting Bits (2011) by tromp on Saturday February 29, 2020 @12:05PM (#22451540)

We can actually solve Towers of Hanoi non-recursively by manipulating bits:

    max = 1 << no_of_discs;
    for (x = 1; x < max; x++)
        printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);

where x&x-1 is smaller than x as much as (x|x-1)+1 is larger than x, by a 2-power corresponding to the least significant 1-bit in x.

[ Parent | on HN ]

Re:From Tower of Hanoi to Counting Bits (2011) by bear8642 on Sunday March 01, 2020 @09:47AM (#22457027)

Could you explain why that's true? - get that it works but don't understand why

[ Parent | on HN ]

Re:From Tower of Hanoi to Counting Bits (2011) by tromp on Monday March 02, 2020 @03:51AM (#22462757)

I never constructed a proof either, but it would rest on the observation that the i'th smallest disc (i=1..no_of_discs) moves every 2^i-th step in the same direction (+1 mod 3 for odd i and -1 mod 3 for even i).

[ Parent | on HN ]