// Towers of Hanoi
// Straightforward iterative solution
//
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// We use three integer variables labeled A, B, and C to
// represent the three stacks.  The disks are numbered
// from 1 to NDISK and a set bit "n" in A/B/C indicates
// that disk number n is in that stack.  A cleared bit
// indicates the disk is not in that stack.  The smallest
// disk is in bit 0, and the largest is in bit NDISK-1.
#define NDISK 5
#define USEMASK (uint32_t)0x0000001f

// Variable A is initialized with the low NDISK bits set.
// Note that if a disk is not in A or B then it must be
// in C.  That is C == ~(A | B) for the first NDISK bits.
// The top-of-stack (tos) is the first LSB set.  A stack
// is empty if no bits are set. An invalid disk is set to
// NODISK.
#define NODISK (uint32_t)(0xffffffff)

// For each stack
//   If the tos is even move it clockwise:  A->B->C->A
//   If the tos is odd move it counterclockwise: A->C->B->A
//   Do not move the same piece twice in a row
// Exactly one stack/disk will be a valid move in each pass.

// The getlsb() routine examines the input integer and 
// replicates just the LSB of the input value.  For example,
// an input of 0x0e46 returns 0x0002.
uint32_t getlsb(uint32_t);

// The idea of odd or even top-of-stack requires comparing
// the value from getlsb() with a mask for ODD.
#define ODDMASK  (uint32_t)0xaaaaaaaa
#define EVENMASK (uint32_t)0x55555555

// Macro definition for getlsb()
#define getlsb(inval) \
            ((inval == 0x0000000) ? NODISK :  \
             (inval & 0x00000001) ? 0x00000001 :  \
             (inval & 0x00000002) ? 0x00000002 :  \
             (inval & 0x00000004) ? 0x00000004 :  \
             (inval & 0x00000008) ? 0x00000008 :  \
             (inval & 0x00000010) ? 0x00000010 :  \
             (inval & 0x00000020) ? 0x00000020 :  \
             (inval & 0x00000040) ? 0x00000040 :  \
             (inval & 0x00000080) ? 0x00000080 :  \
             (inval & 0x00000100) ? 0x00000100 :  \
             (inval & 0x00000200) ? 0x00000200 :  \
             (inval & 0x00000400) ? 0x00000400 :  \
             (inval & 0x00000800) ? 0x00000800 :  \
             (inval & 0x00001000) ? 0x00001000 :  \
             (inval & 0x00002000) ? 0x00002000 :  \
             (inval & 0x00004000) ? 0x00004000 :  \
             (inval & 0x00008000) ? 0x00008000 :  \
             (inval & 0x00010000) ? 0x00010000 :  \
             (inval & 0x00020000) ? 0x00020000 :  \
             (inval & 0x00040000) ? 0x00040000 :  \
             (inval & 0x00080000) ? 0x00080000 :  \
             (inval & 0x00100000) ? 0x00100000 :  \
             (inval & 0x00200000) ? 0x00200000 :  \
             (inval & 0x00400000) ? 0x00400000 :  \
             (inval & 0x00800000) ? 0x00800000 :  \
             (inval & 0x01000000) ? 0x01000000 :  \
             (inval & 0x02000000) ? 0x02000000 :  \
             (inval & 0x04000000) ? 0x04000000 :  \
             (inval & 0x08000000) ? 0x08000000 :  \
             (inval & 0x10000000) ? 0x10000000 :  \
             (inval & 0x20000000) ? 0x20000000 :  \
             (inval & 0x40000000) ? 0x40000000 :  \
             (inval & 0x80000000) ? 0x80000000 : NODISK)

int main()
{
    uint32_t A, B, C;               // stacks 
    uint32_t tosa, tosb, tosc;      // bit set at location of LSB
    uint32_t last;                  // last piece moved
    int      nstep;                 // number of moves taken

    // Initialize variables
    A = USEMASK;
    B = 0;
    C = 0;
    tosa = 1;
    tosb = NODISK;
    tosc = NODISK;
    last = NODISK;
    nstep = 0;


    while(1) {
        //printf("%8d   %04x %04x %04x   %x %x %x -- %x\n", nstep,A,B,C,tosa,tosb,tosc,last); 
        //   If the tos is even move it clockwise:  A->B->C->A
        //   If the tos is odd move it counterclockwise: A->C->B->A
        if ((tosa & EVENMASK) && (tosb > tosa) && (tosa != last)) {
            printf("Move %d from A to B\n", tosa);
            B = B | tosa;        // put disk on stack B
            tosb = tosa;         // set top-of-stack B
            last = tosa;
            A = A & ~tosa;       // remove disk from A
            tosa = getlsb(A);    // get new top-of-stack of A
        }
        else if ((tosa & ODDMASK) && (tosc > tosa) && (tosa != last)) {
            printf("Move %d from A to C\n", tosa);
            C = C | tosa;        // put disk on stack C
            tosc = tosa;         // set top-of-stack C
            last = tosa;
            A = A & ~tosa;       // remove disk from A
            tosa = getlsb(A);    // get new top-of-stack of A
        }
        else if ((tosb & EVENMASK) && (tosc > tosb) && (tosb != last )) {
            printf("Move %d from B to C\n", tosb);
            C = C | tosb;        // put disk on stack C
            tosc = tosb;         // set top-of-stack C
            last = tosb;
            B = B & ~tosb;       // remove disk from B
            tosb = getlsb(B);    // get new top-of-stack of B
        }
        else if ((tosb & ODDMASK ) && (tosa > tosb) && (tosb != last)) {
            printf("Move %d from B to A\n", tosb);
            A = A | tosb;        // put disk on stack A
            tosa = tosb;         // set top-of-stack A
            last = tosb;
            B = B & ~tosb;       // remove disk from B
            tosb = getlsb(B);    // get new top-of-stack of B
        }
        else if ((tosc & EVENMASK) && (tosa > tosc) && (tosc != last)) {
            printf("Move %d from C to A\n", tosc);
            A = A | tosc;        // put disk on stack A
            tosa = tosc;         // set top-of-stack A
            last = tosc;
            C = C & ~tosc;       // remove disk from C
            tosc = getlsb(C);    // get new top-of-stack of C
        }
        else if ((tosc & ODDMASK) && (tosb > tosc) && (tosc != last)) {
            printf("Move %d from C to B\n", tosc);
            B = B | tosc;        // put disk on stack B
            tosb = tosc;         // set top-of-stack B
            last = tosc;
            C = C & ~tosc;       // remove disk from C
            tosc = getlsb(C);    // get new top-of-stack of C
        }
        nstep++;

        if ((B == USEMASK) || (C == USEMASK)) {
            printf("steps = %d\n", nstep);
            exit(0);
        }

    }
}