while and do while Loops

Part I · Module 4 · Chapter 4.4 · while and do while Loops

1. Repetition With a Condition

A while loop is written like an if and behaves differently in exactly one respect: when the controlled statement finishes, the condition is tested again.

#include <stdio.h>

int main(void)
{
    int remaining = 3;

    while (remaining > 0) {
        printf("remaining %d\n", remaining);
        remaining = remaining - 1;
    }

    printf("finished with remaining %d\n", remaining);

    return 0;
}

Output:

remaining 3
remaining 2
remaining 1
finished with remaining 0

Follow the object rather than the text. remaining starts at 3, and the condition and the body take turns:

test remaining > 0   3 > 0   true    body runs, prints 3, remaining becomes 2
test remaining > 0   2 > 0   true    body runs, prints 2, remaining becomes 1
test remaining > 0   1 > 0   true    body runs, prints 1, remaining becomes 0
test remaining > 0   0 > 0   false   loop ends

Four tests and three executions of the body. The condition is checked once more than the body runs, because the loop has to discover that it is finished.

Everything you already know about conditions applies unchanged. It is an ordinary expression, judged against zero by Chapter 2.10's rule. while controls exactly one statement, and the braces make several statements into one, exactly as in Chapter 4.1.

2. A Loop Is Three Obligations

The syntax is two lines. The thinking is three commitments, and only two of them are visible in the keyword.

Initialise the state the condition reads, before the loop. Test that state, in the condition. Change that state, inside the body, in the direction that will eventually make the test fail.

Miss the first and you are testing an object you never wrote to — the bug Chapter 2.3 described. Miss the third and the loop never ends.

Zero is a legal number of iterations

Because the test comes first, a while body may never run at all:

#include <stdio.h>

int main(void)
{
    int remaining = 0;

    printf("before\n");

    while (remaining > 0) {
        printf("this never runs\n");
        remaining = remaining - 1;
    }

    printf("after\n");

    return 0;
}

Output:

before
after

This is a feature, not an accident. A loop that processes however many items there are must cope with there being none, and while gives you that for free.

3. When the Loop Does Not Stop

Two failures produce a program that runs forever. They look similar and the compiler treats them very differently, which is worth seeing.

The stray semicolon

    int remaining = 3;

    while (remaining > 0);
    {
        printf("remaining %d\n", remaining);
        remaining = remaining - 1;
    }

The ; immediately after the condition is an empty statement, and since while controls exactly one statement, that empty statement is the entire body. The braced block below it is not part of the loop at all — it is just a block that follows it, and execution never gets there, because the loop tests remaining > 0 forever with nothing changing remaining.

The compiler notices:

warning: while loop has empty body [-Wempty-body]
note: put the semicolon on a separate line to silence this warning

The body that makes no progress

    int remaining = 3;

    while (remaining > 0) {
        printf("remaining %d\n", remaining);
    }

The braces are right. The body runs. The condition is sensible. And remaining holds 3 forever, because nothing in the body touches it.

Compiled with -Wall -Wextra -Wpedantic, this produces no diagnostic at all. There is nothing for the compiler to object to: a program that runs forever is not an error, and deciding in general whether a loop terminates is not something a compiler can do.

A loop whose condition is a constant — while (1) — is the deliberate version of this, used when the exit is somewhere other than the top of the loop. It needs a mechanism to leave from inside the body, which Chapter 4.6 introduces; until then, every loop in this chapter exits through its condition.

4. do while: Testing After the Body

while tests before the body. The other form tests after it:

#include <stdio.h>

int main(void)
{
    int remaining = 0;

    do {
        printf("body ran with remaining %d\n", remaining);
        remaining = remaining - 1;
    } while (remaining > 0);

    printf("finished\n");

    return 0;
}

Output:

body ran with remaining 0
finished

remaining was 0 before the loop — the same starting value that made §2's while run zero times. Here the body ran once anyway, because the test happens afterwards.

The structural difference is the whole of it:

while               do while

test                 body
body                 test
test                 body
body                 test
test  -> leave       ...
                     test -> leave

body may run         body always runs
zero times           at least once

Two syntactic details are worth noting now rather than discovering later. The condition goes at the end, after the closing brace. And the construct ends with a semicolon — } while (condition); — which is the one place in C where a closing brace is followed by a required semicolon, and the one place everybody forgets it.

5. When do while Is the Right Answer, Not a Preference

The usual advice is "use do while when the body must run at least once", which is true and explains nothing. Here is a case where one of the two is simply wrong.

Counting the decimal digits of a number is a loop: strip a digit, count it, repeat until nothing is left.

#include <stdio.h>

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

    unsigned int with_while = value;
    int digits_while = 0;
    while (with_while > 0u) {
        digits_while = digits_while + 1;
        with_while = with_while / 10u;
    }

    unsigned int with_do = value;
    int digits_do = 0;
    do {
        digits_do = digits_do + 1;
        with_do = with_do / 10u;
    } while (with_do > 0u);

    printf("value %u: while says %d digits, do while says %d digits\n",
           value, digits_while, digits_do);

    return 0;
}

Output:

value 0: while says 0 digits, do while says 1 digits

The number 0 is written with one digit. The while version answers 0, and it is wrong.

The reason is structural rather than arithmetical. The while version asks is there anything left to strip? before stripping anything — and for the value 0 the honest answer is no, so it never counts a digit. The do while version strips first and asks afterwards, which matches the actual rule: every number has at least one digit, even the one whose digit is zero.

Change value to 407 and both versions answer 3. The two forms differ only at the boundary, which is exactly where this kind of bug lives — a counter that is correct for every value you tried by hand and wrong for the empty case you did not.

Choose do while when the first pass is unconditional in the problem, not merely when it happens to be convenient. If you can say "there is always at least one of these", the test belongs at the bottom.

That is a narrow condition, and while is the right choice far more often. But when it applies, while is not a slightly clumsier alternative — it gives a different answer.

6. Two Realistic Loops

Both of these repeat an unknown number of times, which is the situation a loop exists for. Neither could be written as a fixed sequence of statements, because you cannot know while writing the code how many passes the data will need.

Reducing a pair of numbers

Euclid's algorithm finds the greatest common divisor by repeatedly replacing the larger number with the remainder. Chapter 3.3 established exactly what % computes, which is all this needs:

#include <stdio.h>

int main(void)
{
    unsigned int a = 1071u;
    unsigned int b = 462u;

    while (b != 0u) {
        unsigned int remainder = a % b;
        printf("a %-6u b %-6u remainder %u\n", a, b, remainder);
        a = b;
        b = remainder;
    }

    printf("greatest common divisor: %u\n", a);

    return 0;
}

Output:

a 1071   b 462    remainder 147
a 462    b 147    remainder 21
a 147    b 21     remainder 0
greatest common divisor: 21

The progress argument is the interesting part. b is replaced by a % b on every pass, and Chapter 3.3 established that a remainder is smaller in magnitude than the divisor it came from. So b strictly decreases every time, and a strictly decreasing unsigned value cannot decrease forever — it must reach 0, and when it does the loop ends. That is a proof of termination, not a hope, and it is the kind of reasoning that distinguishes a loop you trust from one you have merely tested.

Note also how the example ends: the answer is in a, not b, because the final pass moved it there. Knowing which object holds the result after the loop is part of reading the loop correctly.

Counting set bits

Module 3 gave you the operators for this; a loop is what turns them into an answer for an arbitrary value.

#include <stdio.h>

int main(void)
{
    unsigned int pattern = 0xB4u;
    unsigned int remaining = pattern;
    int set_bits = 0;

    while (remaining != 0u) {
        set_bits = set_bits + (int)(remaining & 1u);
        remaining = remaining >> 1;
    }

    printf("0x%02X has %d bits set\n", pattern, set_bits);

    return 0;
}

Output:

0xB4 has 4 bits set

0xB4 is 1011 0100 in binary, which does have four 1 bits. Each pass inspects the lowest bit with & 1u — Chapter 3.8's masking — and then shifts the value right by one, which Chapter 3.9 established is well defined for an unsigned operand and brings in a zero at the top. So remaining strictly decreases on every pass and must reach 0. The same termination argument as before, from a different direction.

The original pattern is copied into remaining before the loop because the loop destroys what it examines. Keeping the input intact and consuming a copy is a habit worth forming.

7. What You Should Be Able to Say Now

1. A while loop tests a condition, runs its body, and tests again — the first construct that executes a statement more than once.
2. The condition is an ordinary expression, and while controls exactly one statement, exactly like if.
3. A loop is three obligations: initialise the state, test it, and change it in the body.
4. The condition is evaluated one more time than the body runs.
5. A while body can run zero times, which is usually what you want.
6. while (condition); makes the empty statement the body — caught by -Wempty-body.
7. A body that never changes what the condition reads produces no diagnostic at all. That obligation is yours.
8. do while tests after the body, so the body always runs at least once, and the construct ends with a semicolon.
9. Choose do while when the first pass is unconditional in the problem — counting the digits of 0 gives 1 with do while and a wrong 0 with while.
10. A loop you trust comes with a termination argument: name the quantity that strictly decreases.

8. Exercises

Exercise 1 — predict the output. Do not compile yet. Give the exact output and the final value of n.

int n = 4;
while (n > 1) {
    printf("%d ", n);
    n = n / 2;
}
printf("| n = %d\n", n);

Exercise 2 — count the tests. For Exercise 1, say how many times the condition was evaluated and how many times the body ran, and explain why the two numbers differ.

Exercise 3 — trace the state. Write the state table, in the style of §1, for this loop. Then say what it computes.

unsigned int value = 13u;
unsigned int total = 0u;
while (value > 0u) {
    total = total + (value % 10u);
    value = value / 10u;
}

Exercise 4 — find the bug. Each of these runs forever. For each, say which of the three obligations was missed, and whether the compiler would warn.

int i = 0;
while (i < 5);
{
    printf("%d\n", i);
    i++;
}

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

int limit = 10;
int taken = 0;
while (taken < limit) {
    printf("taking one\n");
}

Exercise 5 — repair them. Fix all three from Exercise 4 with the smallest change in each case.

Exercise 6 — choose the form. For each, say whether you would write while or do while, and give the boundary case that settles it: (a) halving a value until it reaches 1; (b) checking a setting and re-checking until it is valid; (c) processing however many retries remain, which may be none; (d) printing the digits of a number.

Exercise 7 — prove it terminates. For §6's bit counter, name the quantity that strictly decreases on every pass and explain why it cannot decrease forever. Then say what would go wrong if remaining were declared int and the pattern had its highest bit set — referring to what Chapter 3.9 says about shifting a signed value.

Exercise 8 — write one. Write a loop that computes the smallest power of two greater than or equal to a given positive unsigned int. State your termination argument before you compile it.

9. Summary

• A while loop evaluates a condition before every pass, so its body may run zero times.
• A loop is initialise, test, change — and only the first two are visible in the syntax.
• The condition runs once more than the body.
• while (c); makes the empty statement the body; -Wempty-body catches it. A body with no progress is caught by nothing.
• do while tests after the body, always runs it at least once, and ends with a semicolon.
• Pick do while when the problem itself guarantees a first pass — the digits of 0 are the case that proves it matters.
• Every loop you write should come with a termination argument: a quantity that strictly decreases.

Both forms keep the three obligations in three different places — the initialisation above the loop, the test in the header, and the change buried somewhere in the body. When a reader has to hunt for the statement that makes progress, they cannot check your termination argument at a glance, and when the body grows, that statement is the one most easily lost in an edit. The next chapter introduces the form that gathers all three into a single line.