wanbo's blog

Why this simple loop runs forever?
By wanbo, 9 years ago, In English

I found this code can not finish in time, anyone knows why it can't finished in 10 iterations? Is it because of something happened to -O2? I do not think the overflow of n will affect the loop if the compiler haven't done some weird work. Sometimes, we need overflow, for example, in rolling hash of string, but why it works properly there and not bellow?

Please help!!!

#include <bits/stdc++.h>
using namespace std;
int main() {
    int cnt = 0;
    for(int n = (1U << 31) - 10; cnt < 10; n++) {
        cout << n << endl;
        cnt++;
    }
    return 0;
}
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Because signed integer overflow is undefined behavior, the compiler is free to assume that it doesn't happen, i.e. cnt is always less than 10. When you need overflow, use unsigned integers.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The signed integer overflow is undefined? What's undefined means here? Is it means the program will out of control even this integer's value isn't important? why cnt is always < 10? you can try to output it, it can bigger than 10, but the loop still do not end, it seems the compiler ignores the end condition of this loop.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +47 Vote: I do not like it

      When your program contains an undefined behavior , a standards conforming compiler can do anything it wants (result of compilation is undefined; in particular, your program could output Shakespeare's Hamlet to stdout). This rule is important to enable many compiler optimizations.

      What Every C Programmer Should Know About Undefined Behavior

      In this particular case, here's what the compiler thinks:

      1. If n is increased by 10 or more, it overflows. This is undefined behavior, so let's assume it doesn't happen. (If it does happen, I can do anything I want anyway).
      2. Each loop iteration increments both cnt and n.
      3. So, cnt can't be increased by 10 or more.
      4. So, cnt<10 is always true. Let's optimize the loop to for(int n = (1U << 31) - 10; true; n++).
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        This really really helps!!!! Thank you :D

        → Reply