Off-by-One Errors and Loop Invariants

Start with the problem

An off-by-one error is a loop that runs one time too many or one time too few. It misses the last item, processes a nonexistent one, or reads a single position past the end of the data. It is the most common bug in loops, and the reason is the fencepost problem: a fence 10 meters long with a post every meter needs 11 posts, because both ends have one.

Here is a loop meant to add the numbers from 1 to n:

for (int i = 1; i < n; ++i) {
    sum = sum + i;
}

For n equal to 3 it produces 3 instead of 6. Nothing about the typing is wrong. The error is in reasoning about the boundaries, and this lesson gives you two tools for that: a convention that makes boundaries predictable, and a way of thinking, the loop invariant, that tells you exactly what a loop computes.

How the idea works

Half-open ranges. A range written [a, b) includes a and excludes b. The loop for (int i = a; i < b; ++i) visits exactly b - a values. Counting from zero, for (int i = 0; i < n; ++i) runs n times and visits 0 to n - 1, which are the positions of n items once arrays arrive. Two adjacent ranges [0, k) and [k, n) join without a gap or an overlap, so nothing is skipped and nothing is processed twice.

Closed ranges. A range written [a, b] includes both ends, uses <=, and contains b - a + 1 values. Use it when the problem is naturally inclusive, such as "the numbers from 1 to n". The extra plus one is the fencepost.

The loop invariant. An invariant is a statement about the variables that is true every time the loop test is about to run. For the sum, the claim is that sum equals the total of 1 + 2 + ... + (i - 1). Three checks prove that a claim helps you:

1. Initialization. The claim is true before the first test. In step 2 of the trace, i is 1 and sum is 0, which is the empty total of 1 to 0.
2. Maintenance. If the claim is true at one test, then one pass of the body and the step makes it true at the next test (steps 5 and 7). In the middle of the body it may be briefly false, as in step 4, and that is allowed.
3. Termination. When the condition fails, the invariant together with the failed condition tells you what you have. This is the step that exposes the bug.

At the end of the trace, i < n is false and i rose by one each time, so i equals n. The invariant then says sum is the total of 1 to n - 1, which is not the total we wanted. If the test were i <= n, the loop would end with i equal to n + 1, and the same invariant would say that sum is the total of 1 to n.

A practical checklist. For any loop, write down the first value, the last value and the number of iterations. Then test it with n equal to 0, 1 and 2: no items, one item, and the smallest case where the first and last items differ.

Why it is correct

The invariant argument is a small induction proof: a base case (initialization), a step (maintenance) and a conclusion (termination). If all three hold, the loop is correct for every n, not only for the values you tried. The proof also needs the loop to end. That follows from a quantity that moves toward the exit condition on every pass: here n - i falls by one each time, and the loop stops when it is no longer positive.

Half-open ranges make the arithmetic simple: the count is the difference of the ends, and ranges concatenate. That is why the C++ standard library describes every sequence by a beginning and an end that is one past the last element, a convention you will meet again with iterators.

What it costs

Correctness, not speed. An off-by-one error rarely costs time. It costs correctness: a wrong total, a missing last item, or a read one position past the end of an array, which is undefined behavior. That last case gives no error message. It may read garbage, crash, or seem fine until the day the neighboring memory changes. One-byte overruns are a classic source of security vulnerabilities.

Choosing the test. The tests i < n, i != n and i <= n each compile to one comparison and one jump, with no difference in speed. Prefer <. With !=, a loop whose variable skips over n, for example because the step is 2, never stops.

Your time. Writing the invariant takes a minute, and running the loop for n equal to 0, 1 and 2 takes seconds. Both are cheap compared with hunting the bug later in a debugger.

Pitfalls and variations

The extra iteration. for (int i = 0; i <= n; ++i) visits n + 1 positions, which is one too many for n items.

Separators. Printing 1, 2, 3 needs n - 1 commas for n items. Print the first item before the loop, or print a separator only when i > 0.

The moving boundary. If the body changes n, the condition rereads the new value on every test, and the loop may behave differently from what its header suggests.

Strings and the zero byte. A string literal such as "Sum: " has five characters but takes six bytes, because of the terminating zero from lesson 2. Counting only the visible characters is an off-by-one error in bytes.

Different tools, different conventions. Slices in some languages exclude the end, while std::string::substr(pos, len) takes a length instead of an end position. Check what the second number means each time.

Variations. A range-based for removes the index arithmetic altogether. And assert(i <= n) from the header <cassert> writes an invariant into the code, so that debug builds check it on every pass and stop at the first violation.

Where it is used

Binary search is the classic place where boundary reasoning decides correctness, and invariants are how it is taught and verified. The same thinking applies to sorting, to string processing, to splitting work into chunks, and to showing page two of a list that starts at item 21. In each case, the habit of asking what is true at the test, and what is true when it fails, replaces guessing with reasoning.

The next lesson, "Functions: Parameters, Return Values and Scope", packages loops and decisions into named pieces you can reuse.