Tower of Hanoi in C

Run it yourself

Save the listing as hanoi.c and run it:

gcc hanoi.c -o hanoi
./hanoi

It prints the seven moves of the three-disk puzzle:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Change the 3 in the call to solve a bigger puzzle. Every disk you add doubles the output, plus one line.

Line by line

Not what each line says — the listing says that — but why it has to be there:

Why those three lines are enough — the correctness proof, the recurrence and the complexity — is on the Tower of Hanoi algorithm page, and holds for every language here.

Counting the moves without undefined behaviour

#include <inttypes.h>
#include <stdio.h>

/* 2^n - 1 for 1 <= n <= 64. Writing (1 << 64) - 1 would be undefined
   behaviour, so start from all 64 bits set and shift the surplus away. */
uint64_t minimum_moves(int n) {
    return UINT64_MAX >> (64 - n);
}

int main(void) {
    int sizes[] = {3, 10, 64};
    for (int i = 0; i < 3; i++) {
        printf("%d disks: %" PRIu64 " moves\n", sizes[i], minimum_moves(sizes[i]));
    }
    return 0;
}

gcc count_moves.c -o count_moves
./count_moves

3 disks: 7 moves
10 disks: 1023 moves
64 disks: 18446744073709551615 moves

2⁶⁴ − 1 fits a uint64_t exactly: it is UINT64_MAX, every one of the 64 bits set. The obvious way to compute it, (UINT64_C(1) << 64) - 1, is not merely wrong in C but undefined. Shifting a value by as many bits as its type has, or more, is undefined behaviour, which means the standard places no requirement on what the program does — and an optimising compiler is entitled to assume it never happens. C++ can turn this exact mistake into a compile error, when the expression is a constant one.

The same trap is much closer than sixty-four disks. With a 32-bit int, 1 << 31 already shifts a bit into the sign position, and that is undefined too. So (1 << n) - 1, the formula in most C tutorials, stops being a correct program at thirty-one disks.

The listing sidesteps both. 2ⁿ − 1 is just the lowest n bits set, so it starts from all 64 bits set and shifts the surplus away: UINT64_MAX >> (64 - n) is valid for every n from 1 to 64. PRIu64, from inttypes.h, expands to whatever format string prints a uint64_t on the platform at hand.

Without recursion, from the bits

#include <stdio.h>

/* No recursion and no towers in memory: every move of the optimal
   solution can be read straight off the binary digits of its number. */
void hanoi_bits(int n) {
    const char *names = n % 2 == 1 ? "ABC" : "ACB";
    unsigned long long total = (1ULL << n) - 1;

    for (unsigned long long m = 1; m <= total; m++) {
        int disk = 1;
        for (unsigned long long bits = m; (bits & 1) == 0; bits >>= 1) {
            disk++;
        }
        int from = (int)((m & (m - 1)) % 3);
        int to = (int)(((m | (m - 1)) + 1) % 3);
        printf("Move disk %d from %c to %c\n", disk, names[from], names[to]);
    }
}

int main(void) {
    hanoi_bits(3);
    return 0;
}

gcc hanoi_bits.c -o hanoi_bits
./hanoi_bits

This loop stores no towers and makes no recursive calls: move m is read straight off the binary digits of m. For move m:

• Disk: one more than the number of trailing zero bits of m.
• Source tower: (m & (m - 1)) % 3
• Destination tower: ((m | (m - 1)) + 1) % 3

The towers come out as numbers 0 to 2, which name A, B and C for an odd number of disks and A, C and B for an even number, because the smallest disk circles the other way. Why a binary counter describes the puzzle so exactly is the subject of Tower of Hanoi and binary.

The inner loop counts the trailing zeros one bit at a time to stay portable. GCC and Clang can do it in one instruction with __builtin_ctzll, and C23 standardises the operation as stdc_trailing_zeros in stdbit.h. The shift in (1ULL << n) - 1 is safe here up to 63 disks — for 64 the loop bound would need the UINT64_MAX form from above.

The same algorithm in other languages

• Tower of Hanoi in PythonRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• Tower of Hanoi in JavaScriptWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Tower of Hanoi in JavaWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Tower of Hanoi in C++Collecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Tower of Hanoi in C#Top-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Frequently asked questions