Interview Question, i = (i++) + i + (++i) explained at a low level

int x = 5; 
x = (x++) + x + (++x);

This piece of code might come up as a Interview question

and you might ever so kindly thank the interviewers for their time and take a dash for the nearest exit because indeed the code looks as hard to understand as it is to read even though it’s a simple expression.

If you break down the calculation to tiny segments you may come up with the answers 16, 17, 18, 19 or something else, Many programmers will see and instantly recognise x++ as the increment number expression and then look on and see ++x, an expression which looks as foreign as can be. If we break down the issue it will become quite clear, lets first recap what you may already know.

x++ – Increment x by 1, the value before incrementing is returned, This can be cancelled out in cases like x := x++; this means that if x=5, x := (x++), the result will x := x,  x++ would set x to 6 but then x = RESULT will initiate and set x to the result which is x before the increment (5), to combat this if you are using x++ by itself you would have it by itself. A good example of this is in loops for (int x = 0; x < 5; x++).

++x – Increment x by 1, the value after incrementing is returned. This means that x := ++x or x := x + 1 where x=5, ++x will return 6 for the expression.

 

Lets take a look at the question again

int x = 5; 
x = (x++) + x + (++x);

We first initialize x to 5.
Then we will set x to (x++) + x + (++x) , lets break this down into smaller manageable chunks.

  • (x++) Increment x and return the value before incrementing this means our value of x is current 5, we increment it to 6 and return 5. Our current result is 5.
  • + x We will add the value of x into the current result, the value of x is 6, so we add 5 and 6 to get 11 as the result
  • + (++x) We will now increment the value of x and add it to the expression, 6 + 1 = 7, 11 + 7 = 18.

So the expression will end with the value of 18.

This is pretty cool that we understand the question but how do computers get to this conclusion?

When we first compile the program in C# the code will be lexed into tokens which state what each character does, in C# white space is ignored so any spaces are skipped over, ; will mark the end of the current expression, in the case of our code something like this will happen:

...

Take ( : Create a new scope
Take x : VAR
Take + : PLUS_SIGN
Take + : | change to INT_INCREMENT_AFTER
Take ) : Close Scope
// Value of this expression is 5

Take + : PLUS_SIGN
Take x : VAR
// Value of this expression is = 6
Take + : PLUS_SIGN
Take ( : New Scope
Take + : PLUS_SIGN
Take + : | change to INT_INCREMENT_BEFORE
Take X : VAR
Take ) : Close scope
// Value of this expression is 7

after being lexed, The tokens will be compiled to CIL / MSIL, Common Instruction Language which is used to run all dotNet based languages like VB.Net, F#.Net, C#.Net etc. Let’s take the code and run it through a compiler and we get the result in a readable IL format.

IL_0000:  nop
IL_0001:  ldc.i4.5
IL_0002:  stloc.0
IL_0003:  ldloc.0
IL_0004:  dup
IL_0005:  ldc.i4.1
IL_0006:  add
IL_0007:  stloc.0
IL_0008:  ldloc.0
IL_0009:  add
IL_000A:  ldloc.0
IL_000B:  ldc.i4.1
IL_000C:  add
IL_000D:  dup
IL_000E:  stloc.0
IL_000F:  add
IL_0010:  stloc.0
IL_0011:  ret

We are greeted with 12 bytes of instructions which can look scary to anyone who has never dabbled with IL, assembly or with byte-code before but don’t worry it’s quite simple but first because CIL is a stack based VM (Virtual Machine) we will need to go over how a stack works (If you already know this skip this part):

 

Function of stacks (Credit: algolist)

A stack is an dynamic array of information but is always adding and removing items from the top, a stack be created using the top or the bottom as a way of storing items, in our case we will be using higher number = newer values are at the top of the stack.

In the diagram R = 0, a = 1, b = 2, b = 3, i = 4 and t = 5.
When we use a stack we keep track of the current location of the topmost item which is known as the stack pointer (sp).

sp in before is 4
sp in push is 5
sp in pop is 4
sp in after is 4

SP will keep track of the current stack pointer, this helps the program keep track of where the current item is and when a item is popped of the stack the computer will just need to decrement SP and no need to clear the value (if the stack goes up to this level later the value will be overwritten with the new value at sp so we are not required to clear the stack items).

Lets now break down the program instructions

  1. nop – This instruction will tell the cpu to ignore this instruction and skip to the next instruction
  2. ldc.i4.1 – This instruction will push the value of 1 onto the stack
  3. ldc.i4.5 – This instruction will push the value of 5 onto the stack
  4. stloc.0 – This will pop the stack onto a local variable at 0
  5. dup – This duplicates the top stack value
  6. add – Pop the top 2 stack values, add them and then push the result onto the stack
  7. ret – Return (possibly with a value)

Now lets review what the instructions look like when commented

// 
// Local Vars:
//    0: x
//

// x = 5
IL_0000:  nop         // No OP
IL_0001:  ldc.i4.5    // Push 5 into the stack
IL_0002:  stloc.0     // Pop stack into x

// x++
IL_0003:  ldloc.0     // Load x into stack (5)
IL_0004:  dup         // Duplicate stack var [stack: 1 = 5, 0 = 5]
IL_0005:  ldc.i4.1    // Push 1 into the stack
IL_0006:  add         // Adds 1 (stack: 1 = 6, 0 = 5)
IL_0007:  stloc.0     // Pop stack into x (x=6), [stack = 5, the ret val]

// + x
IL_0008:  ldloc.0     // Load value of x (6)
IL_0009:  add         // Add the top 2 stack values, 5+6 [stack 0 = 11]

// ++x
IL_000A:  ldloc.0     // Load value of x (6) 
IL_000B:  ldc.i4.1    // Push 1 onto stack [stack 2 = 1, 1 = 6, 0 = 11]
IL_000C:  add         // Add the top 2 stack values, 1+6 [stack 1 = 7, 0 = 11]
IL_000D:  dup         // Duplicate value top value of stack, [stack 2 = 7, 1 = 7, 0 = 11]
IL_000E:  stloc.0     // Store 7 into x [stack 1 = 7, 0 = 11]

// x = ( x++ ) + x + ( ++x );
IL_000F:  add         // Add 7 and 11 = 18, [stack 0 = 18]
IL_0010:  stloc.0     // Store 18 into x
IL_0011:  ret         // Return

 

Now go and put this knowledge to good use, now you understand the basic low level concept operations of a few stack operations you could possibly try to mimic this by writing you’re very own simple stack VM, Bartosz Sypytkowski created a good introduction to VM’s and how to create your own fully working VM with its own instruction set.

One Reply to “Interview Question, i = (i++) + i + (++i) explained at a low level”

Leave a Reply

Your email address will not be published. Required fields are marked *