Loopy C Puzzle

Integer Underflow

Let us talk a little bit about integer underflow and undefined behaviour in C before we discuss the puzzle I want to share in this post.

#include <stdio.h>

int main()
{
    int i;
    for (i = 0; i < 6; i--) {
        printf(".");
    }
    return 0;
}

This code invokes undefined behaviour. The value in variable i decrements to INT_MIN after |INT_MIN| iterations. In the next iteration, there is a negative overflow which is undefined for signed integers in C. On many implementations though, INT_MIN - 1 wraps around to INT_MAX. Since INT_MAX is not less than 6, the loop terminates. With such implementations, this code prints print |INT_MIN| + 1 dots. With 32-bit integers, that amounts to 2147483649 dots. Here is one such example output:

$ gcc -std=c89 -Wall -Wextra -pedantic foo.c && ./a.out | wc -c
2147483649

It is worth noting that the above behaviour is only one of the many possible ones. The code invokes undefined behaviour and the ISO standard imposes no requirements on a specific implementation of the compiler regarding what the behaviour of such code should be. For example, an implementation could also exploit the undefined behaviour to turn the loop into an infinite loop. In fact, GCC does optimise it to an infinite loop if we compile the code with the -O2 option.

# This never terminates!
$ gcc -O2 -std=c89 -Wall -Wextra -pedantic foo.c && ./a.out

Puzzle

Let us take a look at the puzzle now.

for (i = 0; i < 6; i--) {
    printf(".");
}

An obvious solution is to change i-- to i++.

for (i = 0; i < 6; i++) {
    printf(".");
}

There are a few more solutions to this puzzle. One of the solutions is very interesting. We will discuss the interesting solution in detail below.

Solutions

Update on 02 Oct 2011: The puzzle has been solved in the comments section. We will discuss the solutions now. If you want to think about the problem before you see the solutions, this is a good time to pause and think about it. There are spoilers ahead.

Here is a list of some solutions:

• for (i = 0; i < 6; i++)
• for (i = 0; i < 6; ++i)
• for (i = 0; -i < 6; i--)
• for (i = 0; i + 6; i--)
• for (i = 0; i ^= 6; i--)

The last solution involving the bitwise XOR operation is not immediately obvious. A little analysis is required to understand why it works.

Generalisation

Let us generalise the puzzle by replacing \( 6 \) in the loop with an arbitrary positive integer \( n. \) The loop in the last solution now becomes:

for (i = 0; i ^= n; i--) {
    printf(".");
}

If we denote the value of the variable i set by the execution of i ^= n after \( k \) dots are printed as \( f(k), \) then \[ f(k) = \begin{cases} 0 & \text{if } k = 0, \\ n \oplus (f(k - 1) - 1) & \text{if } k > 1 \end{cases} \] where \( k \) is a nonnegative integer, \( n \) is a positive integer, and the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.

Note that \( f(0) \) represents the value of i set by the execution of i ^= n when no dots have been printed yet.

If we can show that \( n \) is the least value of \( k \) for which \( f(k) = 0, \) it would prove that the loop terminates after printing \( n \) dots.

We will see in the next section that for odd values of \( n, \) \[ f(k) = \begin{cases} n & \text{if } k \text{ is even}, \\ 1 & \text{if } k \text{ is odd}. \end{cases} \] Therefore there is no value of \( k \) for which \( f(k) = 0 \) when \( n \) is odd. As a result, the loop never terminates when \( n \) is odd.

We will then see that for even values of \( n \) and \( 0 \leq k \leq n, \) \[ f(k) = 0 \iff k = n. \] Therefore the loop terminates after printing \( n \) dots when \( n \) is even.

Lemmas

We will first prove a few lemmas about some interesting properties of the bitwise XOR operation. We will then use it to prove the claims made in the previous section.

Lemma 1. For an odd positive integer \( n, \) \[ n \oplus (n - 1) = 1 \] where the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.

Proof. Let the binary representation of \( n \) be \( b_m \dots b_1 b_0 \) where \( m \) is a nonnegative integer and \( b_m \) represents the most significant nonzero bit of \( n. \) Since \( n \) is an odd number, \( b_0 = 1. \) Thus \( n \) may be written as \[ b_m \dots b_1 1. \] As a result \( n - 1 \) may be written as \[ b_m \dots b_1 0. \] The bitwise XOR of both binary representations is \( 1. \)

Lemma 2. For a nonnegative integer \( n, \) \[ n \oplus 1 = \begin{cases} n + 1 & \text{if } n \text{ is even}, \\ n - 1 & \text{if } n \text{ is odd}. \end{cases} \] where the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.

Proof. Let the binary representation of \( n \) be \( b_m \dots b_1 b_0 \) where \( m \) is a nonnegative integer and \( b_m \) represents the most significant nonzero bit of \( n. \)

If \( n \) is even, \( b_0 = 0. \) In this case, \( n \) may be written as \( b_m \dots b_1 0. \) Thus \( n \oplus 1 \) may be written as \( b_m \dots b_1 1. \) Therefore \( n \oplus 1 = n + 1. \)

If \( n \) is odd, \( b_0 = 1. \) In this case, \( n \) may be written as \( b_m \dots b_1 1. \) Thus \( n \oplus 1 \) may be written as \( b_m \dots b_1 0. \) Therefore \( n \oplus 1 = n - 1. \)

Note that for odd \( n, \) lemma 1 can also be derived as a corollary of lemma 2 in this manner: \[ k \oplus (k - 1) = k \oplus (k \oplus 1) = (k \oplus k) \oplus 1 = 0 \oplus 1 = 1. \]

Lemma 3. If \( x \) is an even nonnegative integer and \( y \) is an odd positive integer, then \( x \oplus y \) is odd, where the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.

Proof. Let the binary representation of \( x \) be \( b_{xm_x} \dots b_{x1} b_{x0} \) and that of \( y \) be \( b_{ym_y} \dots b_{y1} b_{y0} \) where \( m_x \) and \( m_y \) are nonnegative integers and \( b_{xm_x} \) and \( b_{xm_y} \) represent the most significant nonzero bits of \( x \) and \( y, \) respectively.

Since \( x \) is even, \( b_{x0} = 0. \) Since \( y \) is odd, \( b_{y0} = 1. \)

Let \( z = x \oplus y \) with a binary representation of \( b_{zm_z} \dots b_{z1} b_{z0} \) where \( m_{zm_z} \) is a nonnegative integer and \( b_{zm_z} \) is the most significant nonzero bit of \( z. \)

We get \( b_{z0} = b_{x0} \oplus b_{y0} = 0 \oplus 1 = 1. \) Therefore \( z \) is odd.

Theorems

Theorem 1. Let \( \oplus \) denote bitwise XOR operation on two nonnegative integers and \[ f(k) = \begin{cases} n & \text{if } n = 0, \\ n \oplus (f(n - 1) - 1) & \text{if } n > 1. \end{cases} \] where \( k \) is a nonnegative integer and \( n \) is an odd positive integer. Then \[ f(k) = \begin{cases} n & \text{if } k \text{ is even}, \\ 1 & \text{if } k \text{ is odd}. \end{cases} \]

Proof. This is a proof by mathematical induction. We have \( f(0) = n \) by definition. Therefore the base case holds good.

Let us assume that \( f(k) = n \) for any even \( k \) (induction hypothesis). Let \( k' = k + 1 \) and \( k'' = k + 2. \)

If \( k \) is even, we get \begin{align*} f(k') & = n \oplus (f(k) - 1) && \text{(by definition)} \\ & = n \oplus (n - 1) && \text{(by induction hypothesis)} \\ & = 1 && \text{(by lemma 1)},\\ f(k'') & = n \oplus (f(k') - 1) && \text{(by definition)} \\ & = n \oplus (1 - 1) && \text{(since \( f(k') = 1 \))} \\ & = n \oplus 0 \\ & = n. \end{align*}

Since \( f(k'') = n \) and \( k'' \) is the next even number after \( k, \) the induction step is complete. The induction step shows that for every even \( k, \) \( f(k) = n \) holds good. It also shows that as a result of \( f(k) = n \) for every even \( k, \) we get \( f(k') = 1 \) for every odd \( k'. \)

Theorem 2. Let \( \oplus \) denote bitwise XOR operation on two nonnegative integers and \[ f(k) = \begin{cases} n & \text{if } n = 0, \\ n \oplus (f(n - 1) - 1) & \text{if } n > 1. \end{cases} \] where \( k \) is a nonnegative integer, \( n \) is an even positive integer, and \( 0 \leq k \leq n. \) Then \[ f(k) = 0 \iff k = n. \]

Proof. We will first show by the principle of mathematical induction that for even \( k, \) \( f(k) = n - k. \) We have \( f(0) = n \) by definition, so the base case holds good. Now let us assume that \( f(k) = n - k \) holds good for any even \( k \) where \( 0 \leq k \leq n \) (induction hypothesis).

Since \( n \) is even (by definition) and \( k \) is even (by induction hypothesis), \( f(k) = n - k \) is even. As a result, \( f(k) - 1 \) is odd. By lemma 3, we conclude that \( f(k + 1) = n \oplus (f(k) - 1) \) is odd.

Now we perform the induction step as follows: \begin{align*} f(k + 2) & = n \oplus (f(k + 1) - 1) && \text{(by definition)} \\ & = n \oplus (f(k + 1) \oplus 1) && \text{(by lemma 2 for odd \( n \))} \\ & = n \oplus ((n \oplus (f(k) - 1)) \oplus 1) && \text{(by definition)} \\ & = (n \oplus n ) \oplus ((f(k) - 1) \oplus 1) && \text{(by associativity of XOR)} \\ & = 0 \oplus ((f(k) - 1) \oplus 1) \\ & = (f(k) - 1) \oplus 1 \\ & = (f(k) - 1) - 1 && \text{(from lemma 2 for odd \( n \))} \\ & = f(k) - 2 \\ & = n - k - 2 && \text{(by induction hypothesis).} \end{align*} This completes the induction step and proves that \( f(k) = n - k \) for even \( k \) where \( 0 \leq k \leq n. \)

We have shown above that \( f(k) \) is even for every even \( k \) where \( 0 \leq k \leq n \) which results in \( f(k + 1) \) as odd for every odd \( k + 1. \) This means that \( f(k) \) cannot be \( 0 \) for any odd \( k. \) Therefore \( f(k) = 0 \) is possible only even \( k. \) Solving \( f(k) = n - k = 0, \) we conclude that \( f(k) = 0 \) if and only if \( k = n. \)