3? or 4?

Discussion in 'Mac Programming' started by notjustjay, Feb 15, 2006.

  1. macrumors 603


    Consider this snippet:

    int main(void)
    int n = 0;
    n=(++n) + (++n);
    cout << n << endl;

    To me, the result of this is clearly going to be 3. Indeed, when I try it, that is the answer I get.

    However, my friend claims he consistently gets 4, and is therefore quite confused (as am I). I trust my friend, so I want to put it out to see what others get.

    (Edit: My friend showed me, and indeed, the very same code on his machine does produce 4. He's using g++ 3.3.4 while I had 3.3.)

    Does anyone else get any circumstance in which this does not return 3? And if so, any ideas why it would do so?
  2. macrumors 6502

    You'll get 4 here.

    You're basically saying

    x = 0;
    x = x+1; (x = 1);
    x = x + 1; (x = 2);
    x = x + x; (x = 4)
  3. jsw
    Moderator emeritus


    I think it's a compiler bug. The first ++n should have been stored as a result before the second ++n was evaluated.
  4. macrumors 603


    Yeah, I can see the reasons why it could be one or the other. If the pre-increment expressions are both operated on before the final addition, sure you get 4. If the expressions are evaluated as-you-go, left-to-right, then you get 3.

    I guess the question is, is this a bug, or a matter of preference (by the compiler)? Seems like it could have pretty serious implications if it's so easy to invoke.

    My compiler here at work also says 3, as does Java.
  5. macrumors 6502

    I got 4 when I used my Powerbook here, as well as my linux machine (which doesn't really suprise me, as they're most likely using the same GCC.

  6. jsw
    Moderator emeritus


    Shared bug then, I think, because what the code should be saying is:

    x = 0;
    x' = x+1; (x' = 1)
    x" = x' + 1; (x" = 2)
    x = x' + x"; (x = 3)

    The fact that it's considering the two "(++n)"'s as a single variable and evaluating them serially (n=1, then n=2), then adding them as though they're the same (n=2), means it's a bug.
  7. macrumors 68000


    Using Visual C++ 2005 here at work, I get 4 as well.
  8. Demi-God (Moderator emeritus)


    Sun's complier gave me 4. This is either huge bug in the root of C compilers, or we missing some concept of how compilers works. I'm not sure.
  9. macrumors 601


    afaik, this is an undefined expression in the c++ language because the order of the evaulation of expressions is undefined.

    therefore, neither compiler result is right or wrong, because the result is simply a product of its implemenation of that undefined expression.

    i hope that, IRL, no one's coding like that.
  10. macrumors 68030



    #include <iostream>
    using namespace std;
    int main(void)
    int n = 0;
    int y1, y2, y0;
    y1 = y2 = y0 = 0;
    n=(++n) + (++n);
    cout << "n:  " << n << endl;
    cout << "y1:  " << y1 << endl;
    cout << "y2:  " << y2 << "  y1:  " << y1 << endl; 
    y0 = y1 + y2;
    cout << "y0:  " << y0 << endl;
    n:  4
    y1:  1
    y2:  2  y1:  2
    y0:  4
    this might clear this up...It isn't a bug.

    Think about writing the code in assembly, if you try to write it out your'll get 4.
  11. macrumors 6502

    That's true, that's really ugly code. How did this come up?
  12. macrumors 68030


  13. macrumors 603


    My friend said he and his friend were playing around, so it was probably a contrived example to begin with. He found it interesting that the two of them were getting different answers.

    When I read the code in my head I see 3 (i.e. the x= x' + x'' logic that jsw wrote out above), and that is indeed what my compilers give me, so it confused me as well.

    I suppose the true proof is to see the assembly code generated and verify that it is indeed translating the compound statement into

    n = n + n;
  14. macrumors member


    ok, let;s be serious

    What's the value of i++ + i++?

    by Bjarne Stroustrup himslef...

    it also addresses the issues of

    v = i++;



  15. jsw
    Moderator emeritus


    To quote:

    The important part is the "don't do that"....
  16. macrumors 65816


    Its more than likely because you put ++n rather n++ , that maybe why your getting a different value
    and It is 3
  17. macrumors G4

    a clear example in nonclearity

    I think 3 is correct. But seeing as this is clearly not clear it serves as an example of very poor code. Code should always be clearly writen. pre-iincrements are never easy to understand and all they save is a few characters of typing. Years ago they hinted to the compiler to use some special increment instruction but optimizes are better now.
  18. macrumors 601


    yes, as i said, it's undefined.
  19. macrumors 6502

  20. macrumors 68030



    Unfortunately, code much worse than the OP shows up in real life :(
  21. macrumors 6502

    Fantastic site -- Not that I'm the best programmer, as I'm usually just patching something together to run through data for myself. Even then, my code doesn't look like that.
  22. macrumors 65816


    Yes, this is the correct answer. In C/C++, you cannot refer to an autoincremented variabled in the same statement, as that's undefined.

    Basically, if we break down what i = ++i means, in assembler, we get:

    INCREMENT MemLocation i
    STORE MemLocation i -> MemLocation i

    Sounds straightforward, right? Well, most RISC platforms cannot operate on values in memory, but can only do so in registers. So, we have:

    LOAD MemLocation i -> Register Rx
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync
    STORE Register Rx -> MemLocation i // Do i = ...

    In both cases there's a redundant STORE , but maybe an optimising compiler could take away the second STORE.

    Now, let's look at i = ++i + ++i. Preincrement takes precedence over addition. Also, in this specific case, right to left, or left to right, would not make a difference, but would with a different expression.

    So a parse tree would be built like this:

              /  \
             i    +
                 / \
             pre++  pre++
               |      |
               i      i
    We could write that parse tree as (let me build it in steps) the following. Assume arguments are evaluated left to right:

    assignTo( "++i + ++i", i )
    assignTo( add("++i", "++i"), i )
    assignTo( add( preInc(i), preInc(i) ), i )

    Because the C/C++ language(s) do not define this any further, it all comes down to compiler implementation. So, we're left with a bunch of questions:

    1. Does each call to preInc(i) load i from memory? Or is it preloaded once, and used repeatedly, in a register, or is it lazily loaded on demand?

    2. If preInc loads i into a register, does it save that register back into the memory location i right away?

    So, a simplistic execution of the tree would yield, using lazy evaluation of i:

    // 1st preInc
    LOAD MemLocation i -> Register Rx
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync

    // 2nd preInc
    LOAD MemLocation i -> Register Ry
    STORE Register Ry -> MemLocation i // Keep Ry, i in sync

    ADD Rx,Ry,Rz
    STORE Register Rz -> MemLocation i
    // i = 3

    Here's an optimised version, with preloading and sharing of i:

    LOAD MemLocation i -> Register Rx

    // 1st preInc
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync

    // 2nd preInc
    STORE Register Rx -> MemLocation i // Keep Rx, i in sync

    ADD Rx,Rx,Rz
    STORE Register Rz -> MemLocation i
    // i = 4

    The core of the problem is that when you use ++i or i++ inside of an expression, you're saying, I want to to modify i and pass the value to another part of the expression. Is i in RAM, or a register? Does the other part of the expression go back to i or just use it in the working register?

    Or do we just say, do whatever's fastest on my architecture, with full optimisation:

    // i is only a register, no RAM
    // i = 0;
    // i = ++i + ++i;
    CLR Rx
    INC Rx
    INC Rx
    ADD Rx,Rx,Rx
    // i=4
  23. Cue
    macrumors regular

    Excellent post MarkCollette! Kudos.
  24. macrumors 6502

    Thanks for the detailed analysis. I'm not a computer scientist by trade, so I don't really know assembly and whatnot. Good to know, thanks again for breaking it down for us.
  25. macrumors 65816


    Thanks guys.

    I posted that because I wanted to show how certain programming problems are caused by limitations of how computers work, under the covers, such as this issue of synchronising variables in RAM and registers. This is also the root cause of why accessing variables in multiples threads is unsafe, and so is actually an important issue.

Share This Page