Why is a for loop getting stuck when using a uint64_t counter, whereas a while loop isn't?

This is a bit of a well-known problem when converting from an up-counting to a down-counting loop and using an unsigned loop iterator.

Since unsigned numbers are always positive and have well-defined wrap-around when going below zero, i >= 0 will always be true for an unsigned loop iterator. Compilers often warn against this.

It has nothing to do with for vs while, the comparison expressions used are simply not equivalent. while(i--) is the same as while(i-- != 0) so it performs no range check of the value with relative operators, only an equivalence check. The equivalent for loop would be

for(int i=16; i--; )

Which is strange and bad practice but valid C.

As for how to fix it, one solution I often recommend is don't write a down-counting loop. The best and most readable loop we can write is the idiomatic:

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

The further we divert from that form, the harder the loop is to read and bugs become more probable. We can actually write your example with an up-counting loop:

for(int i=0; i<n; i++)
{
  printf("%"PRIu64" ", n-i-1);
}

By subtracting the loop iterator from the upper limit and then an additional -1, we can achieve the same backwards counting. The loop body looks a bit stranger but now it actually doesn't matter if we use a signed or unsigned loop iterator. And it has the pretty nice advantage that it actually works :)

Alternatively, if we insist on using down-counting with an unsigned iterator, there's not really a pretty way to do it either:

• We could increase the starting value by 1 and change the condition i>0. This might mean we have to adjust the loop body too, since indices end up off by 1.
• We could leave out the for loop condition and add a if(i==0) break; at the end of the loop.
• We could let the iterator deliberately wrap-around and write a strange loop condition like
  i != UINT64_MAX or i != (uint64_t)-1, which looks plain weird.
• We could cast the iterator (int64_t)i >= 0 which is somewhat more readable but introduces implementation-defined behavior to the code.

So the best solution here probably is to drop one of the requirements: either don't write down-counting loop or don't use an unsigned loop iterator.

Side note:

Note that down-counting loops are not faster. It used to be like that back in the days when compilers were horrible at optimization. Namely because an assembler instruction "branch if zero" is usually a few ticks faster than "branch if lower than n" or similar checks that uses a comparison against a number.

However, all modern compilers are well-aware of this and can turn a loop down-counting in the generated machine code if that would make the code faster. So writing down-counting loops on purpose would be a school book example of "premature optimization" these days.

posted 3 days ago

CC BY-SA 4.0

3d ago

Lundin‭

9236 reputation 38 126 1061 170

SE user DU Jiaen provided the following answer, edited by Martin Zabel and found here.

The expression i >= 0 is always true if i is of an unsigned integer type. The alternative and simple way is to change it into:

uint64_t i;
for (i = 15; i != -1; i--) { ... }

This works no matter if i is a signed or an unsigned integer. In the uint64_t case, -1 will first get converted into 0xFFFFFFFFFFFFFFFF and then compared with i.

If you want to get rid of the compile warning, change it into:

i != (uint64_t)-1

but you need to ensure the uint64_t is exactly the type of i.

posted 5 days ago

CC BY-SA 4.0

aura-lsprog-86‭

96 reputation 8 9 15 8

SE user M Oehm provided with the following answer, as it can be found here.

The condition i >= 0 is always true if i is an unsigned type. Decrementing an unsigned zero will not produce a negative value, but the counter will wrap to the maximum representable number for the given type.

C represents ranges with an inclusive lower bound and an exclusive upper bound. For example, an array of N elements has indices 0 through N - 1. The upper bound itself isn't a valid array index.

This convention means that you use a value before incrementing it, but decrement it before using it. Consider a simple stack:

stack[nstack++] = x;      // push a value
x = stack[--nstack];      // pop a value

The same logic goes for loops: When you move forwards, use the value before you increment it:

for (var i = 0; i < N; i++) { use(i); }

When you move backwards, decrement first and then use it:

for (var i = N; i-- > 0; ) { use(i); }

This loop is equivalent to your while. The update section, which happens after processing the body, is empty here. The check is performed on the value before entering the loop; the loop body has the updated value.

This backwards loop might look awkward with the empty update section, but in other ways it is orthogonal to the forward version:

• It uses the actual bounds; there's no need to start with N - 1;
• It works equally well for arbitrary bounds as long as they follow the convention of inclusive lower and exclusive upper bound;
• The test is a pure inequality, not a greater/less-then-or equal comparison.

posted 5 days ago

CC BY-SA 4.0

aura-lsprog-86‭

96 reputation 8 9 15 8