Loopy C Puzzle (2011) | Hacker News Reader

Loopy C Puzzle (2011)

susam.in

43 pointssusam26 comments

Dave, if I see this in one of your PRs, I promise I will lose it man and we will end up in HR

I don't know who Dave is but I like him already.

I'd suggest that instead of all of those ''\( \oplus \) denote bitwise XOR operation on two nonnegative integers'', put that before all your maths into a ''Notation: '' line so that you do not have to repeat yourself.

and I’d suggest delete “on two non-negative integers” which is irrelevant for bitwise operations.

>The value in variable i decrements to INT_MIN after |INT_MIN| + 1 iterations.

Wouldn't it be just after |INT_MIN| iterations?

Running from 0 to -6 is 7 iterations. Running from 0 to INT_MIN is |INT_MIN| + 1 iterations.

>Running from 0 to -6 is 7 iterations.

I guess it depends on your definition of an iteration. I view an iteration as including the iteration expression (i-- in this case) at the end. So during 7 iterations, i-- has executed 7 times, so the value of i is -7. You seem to be saying the iteration expression belongs to the next iteration as opposed to belonging to the currently ending iteration.

I think my view is the widely accepted view. Check out how cppreference rewrites a for loop:

    {
        init_statement
        while ( condition ) {
            statement
            iteration_expression ;
        } 
    }

In our specific case:

    {
        i = 0;
        while (i < 6) {
            printf(".");
            i--;
        }
    }

https://en.cppreference.com/w/cpp/language/for

>> Running from 0 to -6 is 7 iterations.

> I view an iteration as including the iteration expression (i-- in this case) at the end.

Then you should agree that running from 0 to -6 (inclusive) is 7 iterations.

Example:

  #include <stdio.h>

  int main()
  {
      int i;
      for (i = 0; i >= -6; i--, printf("iterated\n")) {
        printf("i = %d\n", i);
      }
      return 0;
  }

Output:

  i = 0
  iterated
  i = -1
  iterated
  i = -2
  iterated
  i = -3
  iterated
  i = -4
  iterated
  i = -5
  iterated
  i = -6
  iterated

7 times through the loop is 6 iterations. It’s the first time that is iterated, repeated.

Isn't the first pass through the body of the loop also often colloquially called "the first iteration"?

Yes, but look at your example here. The value is decremented to -6 after the 6. iteration, right? That’s what Thorrez is saying at the start of this thread.

Thank you for elaborating the terminology issue in your comments. I do see Thorrez's point now.

If we consider an iteration to be complete when i-- (the iteration expression) has been completed execution, then yes, the value of the variable i is decremented to -6 when the 6th iteration completes.

In fact, the value of the variable i is decremented to -7 when the 7th iteration completes. The language used in this blog post regarding the iterations (which is also quoted by Thorrez) is indeed sloppy. I will update it soon and fix it. Thank you, jonsen and Thorrez, for paying attention to the details!

The body of the loop will run |INT_MIN| + 1 times. I don't think there is a more well-accepted definition of "iteration" than that.

> ...well-accepted definition of "iteration"...

To say or perform again; repeat. synonym: repeat. To utter or do again; repeat: as, to iterate an advice or a demand. Repeated.

So x+1 times is x iterations.

I don't think I have ever heard a programmer say that running a piece of code two times is "one iteration".

But they can say both of:

- From 1 to 10 there is 9

- From 1 to 10 there is 10

How far from 0 to INT_MIN - it depends.

None of that affects the fact that if a loop runs 10 times, all programmers will say that it ran for 10 iterations.

Yes. My point here is that Thorrez at the start of this thread may have a point:

Start 0 1. iteration -1 2. iteration -2 3. iteration -3 ... at the end of the |INT_MIN|’th iteration INT_MIN

You may define or argue that it is, but it's not a common sense for anyone.

Agree regarding programming. But this could be common sense:

Start 0 1. iteration -1 2. iteration -2 3. iteration -3 ... at the end of the |INT_MIN|’th iteration INT_MIN

Why are you only including the body of the loop and not the iteration statement? Like I said, cppreference seems to include the iteration statement as part of the iteration.

Because it is the body that people care about when they talk about algorithms.

But even if you include it, it is ran exactly as many times as the body of the loop, so not sure why you bring it up?

>Because it is the body that people care about when they talk about algorithms.

The article isn't just talking about what happens in the body. It's also talking about what the value of i is after an iteration is done.

>But even if you include it, it is ran exactly as many times as the body of the loop, so not sure why you bring it up?

That's exactly why I bring it up:

After 0 iterations, the iteration statement ran 0 times, so i is 0.

After 1 iteration, the iteration statement ran 1 time, so i is -1.

After 2 iterations, the iteration statement ran 2 times, so i is -2.

...

After |INT_MIN| iterations, the iteration statement ran |INT_MIN| times, so i is INT_MIN.

This directly contradicts the article. My point is that the article has an error.

If on the other hand you say the iteration statement isn't part of the iteration you get:

After 0 iterations, the iteration statement ran 0 times, so i is 0.

After 1 iteration, the iteration statement ran 0 times, so i is 0.

After 2 iterations, the iteration statement ran 1 time, so i is -1.

...

After |INT_MIN| + 1 iterations, the iteration statement ran |INT_MIN| times, so i is INT_MIN.

I don't agree with that point of view. But it does agree with the article.

An obvious solution is to change i-- to i++.

Don't know if OP is the author, but the code under the statement is not the correct one

Thanks! That was a copy-paste error. Fixed it now.

Customary links to the 'required reading' blog posts on undefined behaviour in C:

* https://blog.llvm.org/posts/2011-05-13-what-every-c-programm...

* https://blog.regehr.org/archives/213

* https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=63...

Reply on news.ycombinator.com