Hacker News new | ask | show | jobs
From Tower of Hanoi to Counting Bits (2011) (susam.in)
41 points by datanerd 2307 days ago
2 comments
tromp 2307 days ago
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.
link
bear8642 2306 days ago
Could you explain why that's true? - get that it works but don't understand why
link
tromp 2305 days ago
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).
link
dirtydroog 2307 days ago
> It takes O(n*n) time to add the n integers.

Eh?

link
saagarjha 2307 days ago
The time complexity assumption for addition is given earlier in the article.
link
polyphonicist 2307 days ago
From the article:

> We will be dealing with arbitrary precision integers (bignums) in the problem, so let us also make a few assumptions:

> Addition or subtraction of an m-bit integer and an n-bit integer (m <= n) takes O(n) time.

> Counting the number of 1-bits in an n-bit integer takes O(n) time.

link