From Tower of Hanoi to Counting Bits (2011)
1–8 of 8 posts
Re: From Tower of Hanoi to Counting Bits (2011)
#2> It takes O(n*n) time to add the n integers.
Eh?
Re: From Tower of Hanoi to Counting Bits (2011)
#3> It takes O(n*n) time to add the n integers. Eh?
The time complexity assumption for addition is given earlier in the article.
Re: From Tower of Hanoi to Counting Bits (2011)
#4> It takes O(n*n) time to add the n integers. Eh?
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 > Counting the number of 1-bits in an n-bit integer takes O(n) time.
Re: From Tower of Hanoi to Counting Bits (2011)
#5We can actually solve Towers of Hanoi non-recursively by manipulating bits:
max = 1 Re: From Tower of Hanoi to Counting Bits (2011)
#6We can actually solve Towers of Hanoi non-recursively by manipulating bits: max = 1 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.
[deleted]
Re: From Tower of Hanoi to Counting Bits (2011)
#7We can actually solve Towers of Hanoi non-recursively by manipulating bits: max = 1 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.
Could you explain why that's true? - get that it works but don't understand why
Re: From Tower of Hanoi to Counting Bits (2011)
#8We can actually solve Towers of Hanoi non-recursively by manipulating bits: max = 1 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.
Could you explain why that's true? - get that it works but don't understand why
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).