Off-by-One Errors and Infinite Loops

Part I · Module 4 · Chapter 4.7 · Off-by-One Errors and Infinite Loops

1. Two Families

Loop bugs divide almost cleanly in two.

The loop runs the wrong number of times. Usually once too many or once too few — which is why the family is named after being off by one. The program finishes, prints an answer, and the answer is wrong.

The loop never stops. The program does not crash and does not report anything. It just continues, which on a real machine means a process consuming a processor core indefinitely.

The second is more alarming and the first is more dangerous, because an answer that is quietly wrong can travel a long way before anyone questions it.

2. Why "Last Minus First" Is Not a Count

The off-by-one family has one root cause, and it has nothing to do with C. Counting a run of things is not the same as measuring the distance between its ends.

values:    10   11   12   13   14
gaps:         1    2    3    4

Five values. Four gaps between them. 14 - 10 measures the gaps, so it answers 4 — a perfectly correct answer to a question nobody asked.

    int low = 10;
    int high = 14;

    int inclusive = 0;
    for (int v = low; v <= high; v++) {
        inclusive++;
    }

    printf("values %d..%d inclusive: %d of them; high - low is %d\n",
           low, high, inclusive, high - low);

values 10..14 inclusive: 5 of them; high - low is 4

The number of integers from low to high inclusive is high - low + 1.

That + 1 is the fencepost: a fence with five posts has four rails. Every time you compute a count by subtracting two endpoints, stop and decide whether both ends are included.

3. The Three Bounds, Counted

Chapter 4.5 introduced the half-open idiom. Here are the three plausible headers side by side, with the body replaced by a counter so the only thing being measured is the loop:

#include <stdio.h>

int main(void)
{
    int n = 5;
    int count_a = 0;
    int count_b = 0;
    int count_c = 0;

    for (int i = 1; i < n; i++)  { count_a++; }
    for (int i = 1; i <= n; i++) { count_b++; }
    for (int i = 0; i < n; i++)  { count_c++; }

    printf("n = %d\n", n);
    printf("  i = 1; i <  n   ran %d times\n", count_a);
    printf("  i = 1; i <= n   ran %d times\n", count_b);
    printf("  i = 0; i <  n   ran %d times\n", count_c);

    return 0;
}

Output:

n = 5
  i = 1; i <  n   ran 4 times
  i = 1; i <= n   ran 5 times
  i = 0; i <  n   ran 5 times

Three reasonable-looking headers, two different answers. i = 1; i < n is the one that is almost always a mistake — it starts one late and stops one early, and the two errors do not cancel; together they lose exactly one pass.

The habit that removes the whole question:

Write for (int i = 0; i < n; i++) and read it as n times. Any other shape is a decision you should be able to justify out loud.

Check the smallest cases, not the typical one

An off-by-one is almost never visible at n of 5, because being out by one in forty passes looks like forty passes. It is glaring at the boundaries:

The n of 0 row is the one that matters. A loop that is supposed to do nothing when there is nothing to do, and instead does it once, is the bug that survives every test written by somebody who assumed there would always be data. Chapter 4.4's digit counter was the same mistake wearing different clothes — a boundary case nobody tried.

Test your loop with 0 and 1, in your head, before you compile it.

4. Four Ways a Loop Fails to Stop

Nothing changes what the condition reads

Chapter 4.4 §3 established this one. The body is fine, the condition is fine, and no statement in the body touches the object being tested. There is no diagnostic.

The progress goes the wrong way

    int countdown = 5;
    while (countdown > 0) {
        printf("%d\n", countdown);
        countdown = countdown + 1;
    }

There is progress — it is just away from the condition becoming false. A termination argument would have caught this immediately: name the quantity that strictly decreases has no answer here, because the quantity increases.

A continue skips the progress

Chapter 4.6 §3 established this one. In a while loop, continue jumps to the condition, so a progress statement below it never runs on that path. Also no diagnostic.

The condition can never become false

This is the subtlest of the four, because the loop does make progress — just not towards an exit that exists. Two shapes account for almost all of them, and both are consequences of Module 2.

5. The Unsigned Countdown

This is the single most instructive loop bug in C, because it is written by people who were being careful.

    unsigned int n = 3u;

    for (unsigned int i = n; i >= 0u; i--) {
        printf("%u\n", i);
    }

The reasoning behind it is entirely sensible. A count cannot be negative, so unsigned int is the honest type. Counting down to and including zero means continuing while i >= 0. Both steps are defensible, and the loop never ends.

Chapter 2.6 explains why. An unsigned object cannot hold a negative value, so decrementing 0 does not produce −1 — the arithmetic wraps:

#include <stdio.h>
#include <limits.h>

int main(void)
{
    unsigned int i = 0u;

    printf("UINT_MAX is %u\n", UINT_MAX);
    printf("i starts at %u\n", i);

    i = i - 1u;
    printf("after i = i - 1 it holds %u\n", i);

    printf("is 0 >= 0 for unsigned?          %d\n", 0u >= 0u);
    printf("is %u >= 0 for unsigned?  %d\n", i, i >= 0u);

    return 0;
}

Output:

UINT_MAX is 4294967295
i starts at 0
after i = i - 1 it holds 4294967295
is 0 >= 0 for unsigned?          1
is 4294967295 >= 0 for unsigned?  1

Both comparisons answer 1, and they would answer 1 for every other value too. i >= 0u is not a test at all when i is unsigned — every value an unsigned object can hold satisfies it. The loop reaches 0, prints it, decrements to 4294967295, and carries on counting down from there.

This is defined behaviour, incidentally. Chapter 2.6 made the point that unsigned arithmetic is specified to wrap; the program is not undefined, it is simply wrong.

Two repairs are standard. Use a signed control variable, so that −1 exists and i >= 0 can fail:

    for (int i = (int)n - 1; i >= 0; i--) {

Or keep the variable unsigned and test before decrementing, counting down from n to 1 and using i - 1u inside the body:

    for (unsigned int i = n; i > 0u; i--) {
        unsigned int index = i - 1u;
        /* ... */
    }

The second is the one to reach for when the value is genuinely a count or a position, which Module 6 will make the common case.

6. The Floating-Point Loop Counter

The other condition that never becomes false comes from Chapter 2.9.

    for (double x = 0.0; x != 1.0; x = x + 0.1) {

Ten steps of 0.1 should reach 1.0. It does not:

#include <stdio.h>

int main(void)
{
    double x = 0.0;

    for (int step = 0; step < 10; step++) {
        x = x + 0.1;
    }

    printf("after adding 0.1 ten times, x is %.17f\n", x);
    printf("x == 1.0 is %d\n", x == 1.0);

    return 0;
}

Output:

after adding 0.1 ten times, x is 0.99999999999999989
x == 1.0 is 0

The sum lands just below 1.0, so a loop testing x != 1.0 sails past the value it was waiting for and keeps going. Chapter 2.9 established why: 0.1 is not exactly representable, and ten approximations do not add up to an exact 1.

Note how the demonstration is built. The counting is done by an int, and the floating-point value is merely accumulated alongside it — which is also the repair:

Count with an integer. Compute the floating-point value from the count.

    for (int step = 0; step <= 10; step++) {
        double x = step * 0.1;
        /* ... */
    }

The loop now terminates because its control variable is an integer, and x is derived rather than accumulated, so the small errors do not pile up.

7. Prefer < to !=

One more habit prevents a whole category of non-termination. Compare two conditions that look equivalent:

    for (int i = 0; i < 10; i++)
    for (int i = 0; i != 10; i++)

For an ordinary loop they behave identically. They differ when something makes the control variable skip the value it was supposed to stop on:

#include <stdio.h>

int main(void)
{
    int passes = 0;

    for (int i = 0; i < 10; i++) {
        passes = passes + 1;
        if (i == 9) {
            i = i + 1;
        }
    }

    printf("with i < 10 and a value skipped, the loop ended after %d passes\n",
           passes);

    return 0;
}

Output:

with i < 10 and a value skipped, the loop ended after 10 passes

The body pushed i from 9 to 10, the advance pushed it to 11, and 11 < 10 is false — so the loop ended. With i != 10 it would have passed straight over 10 and run forever.

< asks have we got there yet or beyond? and != asks are we exactly there? The first is robust to a control variable that moves unexpectedly; the second is not. Since a control variable moving unexpectedly is itself a bug, this is a case of one habit limiting the damage done by another mistake — which is most of what defensive coding is.

(This also makes §5's second repair safe: i > 0u keeps working even if something inside the body subtracted more than it should.)

8. The Habits, Collected

Nothing in this chapter requires remembering a list of bugs. It requires six habits, each of which is a specific instruction:

1. Write counted loops as for (int i = 0; i < n; i++) and read that header as n times.
2. Remember the fencepost. A count over an inclusive range is high - low + 1.
3. Trace the loop at n of 0 and 1 before compiling it.
4. State the termination argument out loud: which quantity strictly decreases, and what stops it.
5. Count with integers. Never let a floating-point value control a loop.
6. Prefer < to !=, and use a signed control variable when counting down to zero.

And one about tooling: -Wall -Wextra is a starting point, not a complete set. -Wtype-limits would have caught §5 for free.

9. What You Should Be Able to Say Now

1. Loop bugs are mostly two families: the wrong number of passes, and no termination.
2. The number of integers from low to high inclusive is high - low + 1 — subtracting endpoints counts gaps, not values.
3. i = 1; i < n runs n − 1 times; i = 0; i < n and i = 1; i <= n both run n times.
4. Off-by-one errors are invisible at typical sizes and obvious at 0 and 1.
5. A loop fails to terminate when nothing changes, something changes the wrong way, a continue skips the change, or the condition cannot become false.
6. i >= 0 is always true for an unsigned i, so an unsigned countdown never ends — and decrementing 0 gives UINT_MAX, which is defined, not undefined.
7. -Wall -Wextra -Wpedantic does not catch that. -Wtype-limits does.
8. Adding 0.1 ten times gives 0.99999999999999989, so a floating-point loop counter can miss its target entirely.
9. Count with an integer and derive the floating-point value from it.
10. < survives an overshoot; != does not.

10. Exercises

Exercise 1 — count them. Without compiling, say how many times each body runs for n of 7, and then for n of 0.

for (int i = 0; i < n; i++)
for (int i = 1; i <= n; i++)
for (int i = 1; i < n; i++)
for (int i = 0; i <= n; i++)

Exercise 2 — fencepost arithmetic. How many integers are there from 3 to 11 inclusive? From −2 to 2 inclusive? From 7 to 7 inclusive? Give the formula you used.

Exercise 3 — classify four failures. For each, say which of §4's four shapes it is, whether the compiler warns under -Wall -Wextra -Wpedantic, and what the smallest repair is.

int k = 10;
while (k != 0) {
    printf("%d\n", k);
    k = k - 3;
}

unsigned int left = 4u;
while (left >= 0u) {
    printf("%u\n", left);
    left = left - 1u;
}

int t = 0;
while (t < 100) {
    if (t % 7 == 0) {
        continue;
    }
    t = t + 1;
}

double level = 0.0;
while (level != 2.0) {
    level = level + 0.2;
}

Exercise 4 — repair the countdown. Rewrite this so it prints 3, 2, 1, 0 and stops. Apply both repairs from §5 — note that the bounds there count down from n - 1, so you will have to adapt them — and say which you would choose if n were a count of items rather than a starting value.

unsigned int n = 3u;
for (unsigned int i = n; i >= 0u; i--) {
    printf("%u\n", i);
}

Exercise 5 — find the off-by-one. This is meant to print a five-row table. Say what it actually prints, name the mistake, and repair it two different ways.

int rows = 5;
for (int r = 1; r < rows; r++) {
    printf("row %d\n", r);
}

Exercise 6 — explain the warning. Explain in your own words why i >= 0u is reported as always true, and why the compiler can be certain of that without knowing what i holds.

Exercise 7 — debug and repair. This is supposed to report the first three multiples of 5 at or above a starting value. It prints nothing and does not stop. Identify every defect, say which of §4's shapes each one is, then write a corrected version and state its termination argument.

int start = 12;
int found = 0;
int candidate = start;

while (found != 3) {
    if (candidate % 5 != 0) {
        continue;
    }
    printf("%d\n", candidate);
    found = found + 1;
    candidate = candidate + 1;
}

Exercise 8 — design the bounds. You must process a window of readings from index first to index last, both included. Write the for header two ways — once with <= and once converted to a half-open bound — and say how many passes each makes. Then say which you would write and why.

11. Summary

• Most loop bugs are wrong count or no termination, and both have recognisable shapes.
• Subtracting endpoints counts gaps. An inclusive count is high - low + 1.
• i = 0; i < n is the idiom whose count is visible; i = 1; i < n silently loses a pass.
• Off-by-one errors hide at typical sizes. Check 0 and 1.
• Non-termination comes from no progress, progress in the wrong direction, a continue that skips it, or a condition that cannot become false.
• i >= 0 is always true for unsigned — the countdown bug. -Wall -Wextra misses it; -Wtype-limits catches it.
• Floating-point values make bad loop counters. Count with an integer and derive the value.
• Prefer < to !=, so an overshoot ends the loop instead of escaping it.

The module's constructs are now complete, and so is its account of how they fail. One gap remains, and Chapter 4.6 left it open deliberately: break leaves exactly one loop, so a search nested two levels deep has no direct way out and has to carry a flag instead. C does have a statement that transfers control wherever you name — the one with the worst reputation in the language. The final chapter of this module looks at what it actually does, why the reputation is largely deserved, and the two situations in which working C still uses it on purpose.