2011-02-06:

## int a = 5; a = a++ + ++a; a = ?

c:easy
I've received the title riddle from furio and I found it interesting enough to pass it during the next few days to everyone that might be even remotely interested in C/C++ problems. The interesting thing here is the Undefined Behavior (UB), well... actually two UBs, thanks to which there are three possible correct answers: 11, 12 and 13.

Let's start with theoretical considerations on the possible answers and then get to empirical results (initially gathered by nism0, but later extended by readers from the Polish side of the mirror).

OK... so, which places are UB/unknown/compiler-dependent?

First UB
First, we don't know which a will get fetched first (by fetching I mean copying the value from memory to some internal register). There are two possibilities here:

Possibility 1. The first a will get fetched first, then the pre-increment will take place, and then the second a will be fetched (I'll skip the post-incrementation problem for now):
`a = a + ++a;Step 1. Fetch first a.a = 5 + ++a; (a==5)Step 2. Pre-increment a.a = 5 + a;   (a==6)Step 3. Fetch second a.a = 5 + 6;   (a==6)Step 4. Calculate the addition.a = 11;`
Possibility 2. The pre-increment will take place first and the result will be stored in memory, and then the fetching of a will take place.
`a = a + ++a;Step 1. Pre-increment a.a = a + a;   (a==6)Step 2 i 3. Fetching both a.a = 6 + 6;   (a==6)Step 4. Calculate the addition.a = 12;`
So, even with skipping the post-incrementation we get two different possibilities (11 and 12).

Second UB
The second UB is related to the post-incrementation and the potentially trivial line a = a++. As it occurs, there are also two possibilities here (I'll demonstrate them using int a = 5; a = a++; as an example).

Terminology:
a_mem - a still in memory (e.g. as a local variable somewhere on the stack)
a_copy - a previously fetched copy of a in some internal register

Possibility 1. Post-increment goes Missing In Action:
`Initial setup: (a_mem == 5, a_copy == n/a)Step 1. Fetching a.a = 5++; (a_mem == 5, a_copy == 5)Step 2. Post-increment on the variable (in memory).a = 5;   (a_mem == 6, a_copy == 5)Step 3. "Set" gets executed - a_copy is moved to a_mem.(a_mem == 5, a_copy == n/a)`
In the above case the result of post-incrementation went MIA - it got written to the memory but it was soon overwritten by another (not incremented) value. (Actually I've always thought that post-increment is always done after all operations finish so personally I would treat this behavior as a compiler bug.)

Possibility 2. Post-incrementation is deferred to the very end.
`Initial setup: (a_mem == 5, a_copy == n/a)Step 1. Fetching a.a = 5++; (a_mem == 5, a_copy == 5)Step 2. "Set" gets executed - a_copy is moved to a_mem.(a_mem == 5, a_copy == n/a)Step 3. Post-increment on the variable (in memory).a++ (a_mem == 6, a_copy == n/a)`
So, the post-increment is executed at the very end of the calculations and it does not get overwritten.

Summary of UBs
To sum up the two previously described UBs for the a = a++ + ++a equation we get:
Possibilities 1 i 1: 5+6 and the post-increment goes MIA, result: 11
Possibilities 2 i 1: 6+6 and the post-increment goes MIA, result: 12
Possibilities 1 i 2: 5+6 and the post-increment is deferred, result: 12
Possibilities 2 i 2: 6+6 and the post-increment is deferred, result: 13

Experimental results
Now for the empirical results (thx to nism0 for the initial tests and the initial table, and to nonek and qyon for spotting certain typos):

Code 1 Code 2 Code 3 Code 4 Code 5 Code 6
int a = 5;
a = a++ + a++;
int a = 5;
a = a++ + ++a
int a = 5;
a = ++a + a++;
int a = 5;
a = ++a + ++a;
int a = 5;
a = a++;
int a = 5;
a = a + ++a;

Compiler/Lang Ver.Result 1 Result 2 Result 3 Result 4 Result 5 Result 6
gcc 2.9512 13 14 13 6 12
gcc 4.112 13 1413 6 12
gcc 4.212 13 1413 6 12
gcc 4.2.1 Apple 12 13 14 13 6 12
gcc 4.312 13 1413 6 12
gcc 4.3.3 12 13 13 14 6 12
gcc 4.4.4 12 13 13 14 6 12
gcc 4.6.0 (exp.) 12 13 14 13 6 12
gcc 4.5.1 MinGW64 12 13 13 14 6 12
tcc 0.9.25?? ?? ?? ?? 5 12
bcc 0.16.17?? ?? ?? ?? 5 12
Microsoft C/C++ 16.00.30319.01 (80x86)12 13 13 14 6 12
Embarcadero C++ 6.31 for Win32 12 13 13 14 6 12
Intel C++ 12.0.1.127 12 13 13 13 6 12
Keil C 9.02 11 12 12 13 6 12
SDCC 3.0.1 #6092 11 12 13 14 5 12
clang 2.8 11 12 12 13 5 11
clang 1.6 Apple 11 12 12 13 5 11
PHP 5.2.10 11 12 12 13 5 12
java 1.6.0_06 11 12 12 13 5 11
javac 1.4.2_12 11 12 12 13 5 11
java 1.6.0_21 11 12 12 13 5 11
javac 1.6.0_22 11 12 12 13 5 11
C# 2.0 11 12 12 13 5 11
C# 4.0 11 12 12 13 5 11
C# Mono 2.6.4 11 12 12 13 5 11
Borland Turbo C++ for DOS 2.01 12 13 13 14 6 12
HiSoft C for ZX Spectrum 1.3 11 12 12 13 5 12

Thanks for additional results to: Icewall, Krzysztof Kotowicz (PHP 5.2.10), mlen (2x clang, 2x gcc), none'a (2x Java), Keraj (2x Java), MDobak (SDCC & Keil C), garbaty lamer (3x C#, Turbo C++, HiSoft C), Xgrzyb90 (gcc 4.4.4), no_name (gcc 4.3.3), dikamilo (mingw64 4.5.1)

Garbaty lamer has also posted (in the comments on the Polish side of the mirror) a really cool screenshot from the HiSoft C for ZX spectrum (click to zoom):

If you would like to test your compiler (posting back the results in the comments is really appreciated, especially from strange/uncommon compilers and other languages which support pre- / post- increments ;>) you can use the code (made by nism0) at the bottom of the post (see Appendix 3).

And that's that ;>

Appendix 1:
In the comments on the Polish side of the mirror Rolek has suggested to apply the same test to overloaded operators (see the comments on the Polish side for the code). Results (by Rolek from MSVC++ and me from g++):
Code 1 Code 2 Code 3 Code 4 Code 5 Code 6
int a = 5;
a = a++ + a++;
int a = 5;
a = a++ + ++a
int a = 5;
a = ++a + a++;
int a = 5;
a = ++a + ++a;
int a = 5;
a = a++;
int a = 5;
a = a + ++a;

Compiler/Lang. Ver.Result 1 Result  2 Result 3 Result 4 Result 5 Result 6

Also, krlm has posted a link to a good article about sequence points.

Appendix 2:
Garbaty lamer (again, on the Polish side of the mirror) has mentioned that in C# this riddle isn't actually a riddle - it's well defined behavior, see C# specification point §7.3:
Operands in an expression are evaluated from left to right. For example, in F(i) + G(i++) * H(i), method F is called using the old value of i, then method G is called with the old value of i, and, finally, method H is called with the new value of i. This is separate from and unrelated to operator precedence.

Appendix 3:
Code for testing:
`#include <stdio.h>int main(void){  int a = 5, b = 5, c = 5, d = 5, e = 5, f = 5;  // test 1  a = a++ + a++;  printf("%i \n",a);  // test 2  b = b++ + ++b;  printf("%i \n",b);  // test 3  c = ++c + c++;  printf("%i \n",c);  // test 4  d = ++d + ++d;  printf("%i \n",d);  // test 5  e = e++;  printf("%i \n",e);  // test 6  f = f + ++f;  printf("%i \n",f);  // done  return 0;}`

Appendix 4:
A comment from Cem Paya:
--start--
Similar to C#, this is also not a riddle for Java because Java defines
evaluation to be strictly left-to-right.
See section 15.7 here for some examples with side-effects as in your case:
http://java.sun.com/docs/books/jls/second_edition/html/expressions.doc.html
In C++ where it is undefined, the result can also depend on the
optimization level used during compilation, which can change the
number of times a value is referenced. eg the compiler expects "a" to
not change its value during the evaluation and may optimize other
occurences to the same one it fetched.

==end==

2011-02-14 13:33:07 = Love4Boobies
{
Hi,

I've only quickly skimmed through this post but it's not really correct. There aren't only 3 "correct" answers---the whole point of undefined behavior is that anything can happen (e.g., you can even get an error at compile time or have random pixels drawn over the screen instead of anything meaningful happening).

However, if you're looking for likely results, it's still incorrect. There are still serial CPUs to take into account. As with most C operations, a++ and ++a are not atomic so you may end up with a mix of bits from both operations.

Cheers,
Bogdan
}
2011-02-15 10:34:46 = Gynvael Coldwind
{
Hey l4b ;)

As for UB, well, theoretically you are correct. However, from a practical point of view, is there any currently existing C/C++ compiler/interpreter that will generate code, which after execution output a different result than 11, 12 or 13, i.e. draw a random pixel on the screen or sth? If so, please paste it's name & platform, it will be an interesting addition to both the empirical and theoretical studies from the post.

As for serial CPUs, I'm not really familiar of the concept. Seems I need to look into this ;)

Still, a mix of bits from both operations might be interesting, however the results might still fall into the 11-13 range, maybe adding result "10" (however that would be a serious *compiler* misbehavior imo).

Cheers,
}
2012-02-07 12:28:12 = winspool
{
i386-win32-tcc and x86_64-win32-tcc (current mob):
11 12 12 13 5 12

OpenWatcom 1.9 (linux/wcl386, win16/wcl, win32/wcl386)
11 12 13 14 5 12

gcc 4.6.1
12 13 13 14 6 12

}
2016-05-22 04:11:45 = Horcurx
{
Intel(R) Core(TM) i5-4300U / Ubuntu 14.04.2 LTS / x86_64 / gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.1)
11 12 13 14 5 12
}