Simplifying this equation

[Kalcor]

Can someone simplify this equation so it could be understood?
s[i]^= s[j] ^=s[i] ^= s[j];
assuming its put under a nested loop j being inner and i being outer

I tried expanding it but the compiler barked about lvalues and blah blah so idk how to read it or even understand it xD

[ne555]

I'll guess undefined behaviour.

$ clang++ foo.cpp
warning: unsequenced modification and access to 'a' [-Wunsequenced]
        a ^= b ^= a ^= b;
          ~~        ^
1 warning generated.

> I tried expanding it but the compiler barked about lvalues and blah blah
ah, the «blah blah» error.
it's fine that you don't know what the error means, but perhaps we do.

[Kalcor]

@ne555:

It works well, no undefined behavior:

Consider
http://codeforces.com/problemset/problem/339/A

and it's solution:

#include<cstdio>

char s[200];

int main()
{
	int i,j;
	scanf("%s",s);
    for(i=0;s[i];i+=2)
    for(j=i;s[j];j+=2)
    if(s[i]>s[j])
    s[i]^=s[j]^=s[i]^=s[j];

    puts(s);
}

It works perfectly. I don't know what the s[i]^=s[j]^=s[i]^=s[j]; is supposed to mean. I only know that ^ means XOR but other than that idk how this equation works when read by the compiler

[TheIdeasMan]

^= is a compound assignment operator.
So a ^= b is the same as a = a ^ b


http://en.cppreference.com/w/cpp/language/operator_assignment

It is not UB because the subscripts i and j are not being changed, just their corresponding values in the array.

To me, the problem just involves sorting the numbers in the equation: this is an elaborate way of doing this.

[JLBorges]

> Tt works well, no undefined behavior

The behaviour is well defined by C++17; prior to that it used to be undefined behaviour.

In C++17, s[i]^=s[j]^=s[i]^=s[j]; means:

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

See: https://en.wikipedia.org/wiki/XOR_swap_algorithm

A cleaner version of the program, using the same overall logic would be:

#include <iostream>
#include <iomanip>

int main()
{
    char expr[200] {} ;
    std::cin >> std::setw( sizeof(expr) ) >> expr ; // avoid buffer overflow on input
                                                    // or better, use std::string

    // sort the characters in even positions 0, 2, 4 ... in ascending order
    // (assumes that the input is well formed)
    for( int i=0 ; expr[i] != 0 ; i +=2 )
    {
        for( int j = i ; expr[j] != 0 ; j += 2 )
        {
            if( expr[i] > expr[j] )
            {
                const char temp = expr[i] ;
                expr[i] = expr[j] ;
                expr[j] = temp ;

                // or use std::swap
            }
        }
    }
    std::cout << expr << '\n' ;
}

[Kalcor]

Thanks JL! :D

[Cubbi]

Bliink wrote:

It works well, no undefined behavior:

to make sure it's mentioned, "works well" means nothing when you have an undefined program (and that program is undefined except in the upcoming C++17). Working in the manner you consider to be "well" is just one of infinite possible outcomes - changing platform, compiler, compiler version, surrounding code can change outcomes of such programs.

[TheIdeasMan]

@JLBorges, @Cubbi

There is a couple of things that bother me about this code being UB. I know that the compiler may not necessarily issue a diagnostic about UB - maybe this example is too esoteric? Maybe gcc and clang do the expected (?) thing, some other compiler may not?

However:

I couldn't get any of the gcc or clang compilers to give a warning about it: I tried everything from C89 onwards. Most interestingly g++7.1 didn't mention anything - I discovered recently that it issues sequence warnings despite it being legal c++17.

The other thing is that this example is quite different from other examples about sequence points (that I have seen): it is a series of compound assignment sub expressions. Could that mean the compiler is forced to evaluate them right to left? I found this in the C++14 draft standard:

c14draft_standard wrote:

5.18

1 Assignment and compound assignment operators [expr.ass]

The assignment operator (=) and the compound assignment operators all group right-to-left. All require a
modifiable lvalue as their left operand and return an lvalue referring to the left operand. The result in all
cases is a bit-field if the left operand is a bit-field. In all cases, the assignment is sequenced after the value
computation of the right and left operands, and before the value computation of the assignment expression.
With respect to an indeterminately-sequenced function call, the operation of a compound assignment is
a single evaluation. [ Note: Therefore, a function call shall not intervene between the lvalue-to-rvalue
conversion and the side effect associated with any single compound assignment operator. — end note ]

I haven't included clauses 2 through 9.2, they didn't seem to apply. Emphasis added by me.

For the part I underlined, I understand that the left and right side are evaluated first, but what does "...and before the value computation of the assignment expression" mean?

I am not sure whether there is another part of the standard which applies, although I have read section 1.9 (13 to 15)

OTOH, there are warnings about this silly example:

int a = 5;
int b = 3;

a = b = a = b;

But they go away when the operator is changed to ^=, I observe that ^= alters the value, while = does not.

Maybe everything I have said in this post demonstrates the trickiness of UB? Or is this particular question an exception to the other sequencing rules?

I guess the other elephant in the room is to not write code that is too tricky for it's own good: that is, write the xor swap idiom on 3 lines; don't confuse by writing it on 1 line. Sometimes simple is better :+) Edit: Even better just use std::swap

[JLBorges]

We need to distinguish between the two parts of the evaluation of an expression: value computation and side effect.
See: http://en.cppreference.com/w/cpp/language/eval_order

That "the assignment is sequenced after the value computation of the right and left operands, and before the value computation of the assignment expression" - that the value computations are sequenced does not imply that the side effects are also sequenced.

It is only in C++17 (DIS) that this sentence was added to the quoted clause, immediately after the underlined part: "The right operand is sequenced before the left operand".

Therefore since C++17:

20) In every simple assignment expression E1=E2 and every compound assignment expression E1@=E2, every value computation and side-effect of E2 is sequenced before every value computation and side effect of E1
http://en.cppreference.com/w/cpp/language/eval_order

> I couldn't get any of the gcc or clang compilers to give a warning about it

int main()
{
    int a = 0 ;
    int b = 0 ;
    
    a = b = a = b ; // C++14: clang++ does not issue a UB warning for this, but g++ does
    
    a += b *= a ^= b ; // C++14: g++ does not issue a UB warning for this, but clang++ does
}

http://coliru.stacked-crooked.com/a/8687c9f9b6e33790

[Cubbi]

Or is this particular question an exception to the other sequencing rules?

it's not an exception from sequencing rules, but it appears to be complex enough to avoid being flagged by gcc or clang

Let's walk through C++14

the expression is s[i]^=s[j]^=s[i]^=s[j].

First, apply "group right-to-left", and get
s[i] ^= (s[j] ^= (s[i] ^= s[j]))

now look at the leftmost ^=, whose left operand is s[i] and whose right operand is (s[j] ^= (s[i] ^= s[j]))

Your quote says "the assignment is sequenced after the value computation of the right and left operands" - fine, but irrelevant. What you want to know is how are the left and right operands sequenced with respect to each other.

C++17 added to this paragraph "The right operand is sequenced before the left operand", but C++14 does not have that. in C++14 you'll have to go to [intro.execution]p15
"Except where noted, evaluations of operands of individual operators ... are unsequenced"

this means evaluations of s[i] and of (s[j] ^= (s[i] ^= s[j])) are unsequenced.

Now we got to undefined behavior (same paragraph): "If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, and they are not potentially concurrent (1.10), the behavior is undefined.".

Here, value computation of s[i] (read from memory) in the left operand is unsequenced relative to both value computation (read from memory) and side-effect (write to memory) made to s[i] within (s[j] ^= (s[i] ^= s[j])). Therefore, undefined behavior.

[TheIdeasMan]

@JLBorges, @Cubbi

Thanks to you both for your always expert answers - Cheers :+)