Iterating over all unsigned integers in a for loop

Question

Let's say I want to iterate over all integers in a for loop. For the sake of discussion, assume I am calling some unknown function f(unsigned x) for each integer:

for (unsigned i = 0; i < UINT_MAX; i++) {
     f(i);
}

Of course, the above fails to iterate over all integers, because it misses one: UINT_MAX. Changing the condition to i <= UINT_MAX just results in an infinite loop, because that's a tautology.

You can do it with a do-while loop, but you lose all the niceties of the for syntax.

Can I have my cake (for loops) and eat it too (iterate over all integers)?

Answer 1

You'll have to perform the test at the end of the loop body, much like a do-while:

for (unsigned int i = 0; /* nothing */; i++) {
    ...
    if (i == UINT_MAX) {
        break;
    }
}

For a test in the standard for loop test position to work, you would need to track the current iteration in a way that can distinguish between UINT_MAX+2 states: one for each time you enter the loop body, and one for the one time you don't. A single unsigned int can't handle that, so you'd need at least one auxiliary variable or a bigger loop counter.

Answer 2

You can do it with a do-while loop, but you lose all the niceties of the for syntax.

It is still doable with do-while loop by using an anonymous block scope:

{
    unsigned i = 0;
    do { f(i); } while (++i != 0);
}

While this construct may not be most idiomatic, it is an obvious candidate for clear assembly code. For example, gcc -O compiles it as:

.L2:
        mov     edi, ebx   ; ebx starts with zero
        call    f
        add     rbx, 1
        cmp     rbx, rbp   ; rbp is set with 4294967296
        jne     .L2

Answer 3

You could use another variable to detect when you've looped around.

for (unsigned int i = 0, repeat = 0; !(i == 0 && repeat); i++, repeat = 1) {
    ...
}

Answer 4

The classic way to implement your iteration efficiently, with a single test, is a do / while loop:

unsigned i = 0;
do { f(i); } while (i++ != UINT_MAX);

If you insist on using a for loop:

for (unsigned i = 0;; i++) {
    f(i);
    if (i == UINT_MAX)
        break;
}

Here is another variant with 2 variables where all the logic is inside the for expressions:

for (unsigned int i = 0, not_done = 1; not_done; not_done = (i++ - UINT_MAX)) {
    f(i);
}

It might produce slower code because of the extra variable, but as BeeOnRope commented, clang and icc compile it to very efficient code.

Answer 5

An easy solution would be,

unsigned i;
for (i=0; i<UINT_MAX; i++) {
  f(i);
}
f(i);  // i will be UINT_MAX at this time.

Answer 6

Use a larger integer type:

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

int main() {
    for (unsigned long i = 0; i <= UINT_MAX; i++) {
        f(i);
    }
}

This version uses stdint for more consistency

#include <stdio.h>
#include <stdint.h>

int main() {
    for (uint_fast64_t i = 0; i <= UINT32_MAX; ++i) {
        f(i);
    }
}