Consider the following segment of C code: int j, n; j = 1; while (j <= n) j =…

When a loop variable starts at a base value and is repeatedly doubled until it exceeds a bound, the number of times the loop body actually executes equals one more than the largest exponent e for which 2e does not exceed the bound — the body runs once for every exponent from 0 up to and including that largest one, and the one failing test that follows is the loop's exit, not an extra execution.

1. Track j through the loop: it starts at j = 1 = 20, and after every body execution it doubles, so after m completed executions j = 2m.

2. The body executes its (m+1)-th time exactly when the current value 2m still satisfies 2m <= n — that is, body execution number (m+1) happens for every m with 2m <= n.

3. The largest such m is [log2 n] — the largest exponent e for which 2e does not exceed n — so the body executes for m = 0, 1, 2, ..., [log2 n], that is [log2 n] + 1 times in total.

4. The very next test happens for m = [log2 n] + 1, where j has doubled one more time and now exceeds n, so the test comes back false and ends the loop — this test performs no body execution, so it is the loop exiting, not an additional iteration.

Checking this against small cases confirms it:

• n = 4: j = 1 (1<=4, body runs, j becomes 2), j = 2 (2<=4, body runs, j becomes 4), j = 4 (4<=4, body runs, j becomes 8), j = 8 (8<=4, false, loop exits). The body ran 3 times, and [log2 4] + 1 = 2 + 1 = 3 — matching.

• n = 1: j = 1 (1<=1, body runs, j becomes 2), j = 2 (2<=1, false, loop exits). The body ran 1 time, and [log2 1] + 1 = 0 + 1 = 1 — matching.

So for any n > 0 for which this arithmetic stays within the range int can represent (no overflow), the number of iterations made in the execution of the loop is [log2 n] + 1.