Proper way to count down with unsigned

Question

I am reading Carnegie Mellon slides on computer systems for my quiz. In the slide page 49 :

Counting Down with Unsigned
Proper way to use unsigned as loop index

unsigned i; 
for (i = cnt-2; i < cnt; i--) 
a[i] += a[i+1]; 

Even better

size_t i; 
for (i = cnt-2; i < cnt; i--) 
a[i] += a[i+1];   

I don't get why it's not going to be infinite loop. I am decrementing i and it is unsigned so it should be always less than cnt. Please explain.

Rashida

Anything wrong with unsigned i = cnt - 1; while (i--) a[i] = a[i+1];? – Synthiasyntonic

@DavidC.Rankin Robert Seacord of secure coding in c and c++ recommends the latter because length will be then about the size of word. – Rashida

Possible duplicate of Why does counting down an unsigned int loop forever in C? – Malraux

Answer 1

This appears to be an alternative expression of the established idiom for implementing the same thing

for (unsigned i = N; i != -1; --i) 
   ...;

They simply replaced the more readable condition of i != -1 with a slightly more cryptic i < cnt. When 0 is decremented in the unsigned domain it actually wraps around to the UINT_MAX value, which compares equal to -1 (in the unsigned domain) and which is greater than or equal to cnt. So, either i != -1 or i < cnt works as a condition for continuing iterations.

Why would they do it that way specifically? Apparently because they start from cnt - 2 and the value of cnt can be smaller than 2, in which case their condition does indeed work properly (and i != -1 doesn't). Aside from such situations there's no reason to involve cnt into the termination condition. One might say that an even better idea would be to pre-check the value of cnt and then use the i != -1 idiom

if (cnt >= 2)
  for (unsigned i = cnt - 2; i != -1; --i) 
     ...;

Note, BTW, that as long as the starting value of i is known to be non-negative, the implementation based on the i != -1 condition works regardless of whether i is signed or unsigned.

Appoint

It does i < cnt have the advantage of working for cnt = 0 though. – Upright

There are a great deal of correct candidate solutions for this question but yours is more detailed. Thanks! – Rashida

I don't believe this is supported, error: comparison of constant -1 with expression of type 'uint8_t' (aka 'unsigned char') is always true – Malraux

This may fail for other data types but unsigned: E.g for unsigned char (unsigned char)(-1)=255!=-1. – Faddish

Answer 2

The best option for down counting loops I have found so far is to use

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

This invokes the loop body with i=N-1 ... 0. This works the same way for both signed and unsigned data types and does not rely on any overflows.

Faddish

For some reason this answer did not get proper attention. – Perspiration

Answer 3

This loop is simply relying on the fact that i will be decremented past 0, which makes it the max uint value. Which breaks the loop because now i < cnt == false.

Per Overflowing of Unsigned Int:

unsigned numbers can't overflow, but instead wrap around using the properties of modulo.

Both the C and C++ standard guarantee this uint wrapping behavior, but it's undefined for signed integers.

Ovovitellin

Answer 4

It's taking advantage of what happens when you decrement unsigned integer 0. Here's a simple example.

unsigned cnt = 2;
for (int i = 0; i < 5; i++) {
    printf("%u\n", cnt);
    cnt--;
}

That produces...

2
1
0
4294967295
4294967294

Unsigned integer 0 - 1 becomes UINT_MAX. So instead of looking for -1, you watch for when your counter becomes bigger than its initial state.

Simplifying the example a bit, here's how you can count down to 0 from 5 (exclusive).

unsigned i;
unsigned cnt = 5;
for (i = cnt-1; i < cnt; i--) {
    printf("%d\n", i);
}

That prints:

4
3
2
1
0

On the final iteration i = UINT_MAX which is guaranteed to be larger than cnt so i < cnt is false.

size_t is "better" because it's unsigned and it's as big as the biggest thing in C, so you don't have to ensure that cnt is the same type as i.

Lactary

Which produces the same iteration as unsigned i = cnt - 1; while (i--) printf("%u\n", i); but making use of the post-decrement operator which allows evaluating i=0 within the body of the loop before terminating on the condition of while (0) on the next check (prior to the post-decrement). – Synthiasyntonic

Answer 5

The goal of the loops is to loop from cnt-2 down to 0. It achieves the effect of writing i >= 0.

The previous slide correctly talks about why a loop condition of i >= 0 doesn't work. Unsigned numbers are always greater than or equal to 0, so such a condition would be vacuously true. A loop condition of i < cnt ends up looping until i goes past 0 and wraps around. When you decrement an unsigned 0 it becomes UINT_MAX (2³² - 1 for a 32-bit integer). When that happens, i < cnt is guaranteed to be false, and the loop terminates.

I would not write loops like this. It is technically correct but very poor style. Good code is not just correct, it is readable, so others can easily figure out what it's doing.

Yonah

Answer 6

I think you are confused with int and unsigned int data types. These two are different. In the int datatype (2 byte storage size), you have its range from -32,768 to 32,767 whereas in the unsigned int datatype (2 byte storage size). you have the range from 0 to 65,535 . In the above example mentioned, you are using the variable i of type unsigned int. It will decrements up to i=0 and then ends the for loop as per the semantics.

Mcginley