algorithm - binary representation of all states in tower of hanoi -
in modified toh have 4 pegs. in turn have total of 4^n disk positions. in 1 of solutions going through, given state represented using below code -
for(int disc = 0; disc < n; disc++){ state += tower[disc]<<(disc*2); }
tower[disc] --> tower disc located, can (0,1,2,3)
if use n=3 in above code, gives me 63, 4^n -1. formula works, i.e 0-63 64 positions can represented. not able understand mathematical correlation.
can please explain how above formula can represent possible disk positions , how change if further change number of pegs or n lets 5.
since have 4 pegs, position of disk can encoded in 2 bits (00, 01, 10, 11 => 0, 1, 2, 3
). multiplication 2 gives each disk 2 bits of independent memory space within integer state
, first disk starting @ bit 0, second @ bit 2, , on... i
th disk @ (i - 1) * 2
. left shift <<
moves data each disk correct bit position.
however code can "unsafe" - if there mistake in game logic somewhere else caused value of tower
greater 3
, when shifted overflow designated 2 bits of space. prevent this, bitwise , clamp data [0, 3]:
state += (tower[disc] & 3) << (i * 2);
note can use bitwise or instead of addition - state |= ...
.
from example n = 3
provided looks plates starting peg 4 (i.e. tower[3]
). if change n = 5
once again give 4^n - 1 = 1023
, bits below n * 2
set 1.
Comments
Post a Comment