33 replies to this topic

[bladder]

:wallbash: argh...

Ok ok, hold on, so the above would translate to:

op-=( a, op+=( b, op-=( a, op=( b, op-( b ) ) ) ) )

mhmm... i see i see...

Man they keep on saying that it's easy to get caught if you don't read the standard specs. But I gotta say, the more I'm reading the specs the more I'm getting confused. All that monkey business about sequence points ->

the following quote+reply is a preemptive strike in-case davperman reads this:

davperman said:

... some stuff... use c# ...more stuff...

ok.

[bladder]

Yo! .oisyn!!! You have some explaining to do:

I went back to all this stuff and searched some on undefined behavior and found some... "stuff". Now a statement such as:

i = i++;

is undefined right? because the standard claims that you cannot modify the same value between sequence points. Associativity doesnt come into play in the above.

So looking at that += stuff in the same light as i = i++ we have:

i = i += whatever;

The exact words of the standard are:

"Except where noted, the order of evaluation of operands of individual operators and subexpressions of individual expressions, and the order in which side effects take place, is unspecified. Between the previous and next sequence point a scalar object shall have its stored value modified at most once by the evaluation of an expression." [from 5.0.4]

but in the above expression, it's being modified twice, so it should be undefined. So while it is defined by associativity, the actual evaluation of the internal representation on i is undefined, so the value of i is undefined after the expression (a direct effect of undefined order of evaluation)

if you we're going by associativity, the i = i++ should also be defined that way:

op=(i, op++(i))

or for a = a+= b;

op=(a, op+=(a, )

[edit]
Another way of putting it, the expr "a -= b += a -= b = -b;" does the following:

A: assign negative b to b
B: subtract b from a
C: add a to b
D: subtract b from a

The sequence points statement says that the order of eval is undefined so it could be ABCD or ACDB or BCDA, etc... I'm not saying the above won't work, but it's still undefined according to the standard (sigh... again if i'm understanding all this correctly)
[/edit]

[davepermen]

bladder said:

the following quote+reply is a preemptive strike in-case davperman reads this:

more important: learn my name

[bladder]

apologies davepermen - believe it or not, i was expecting such a reply from you . I was unsure when typing the spelling and i recalled you would always grab anyone who didn't spell your name correctly. But I just didn't have the time to search for the correct spelling.

[martinsm]

C++:

std::swap(x, y);

Python:

x, y = y, x

[.oisyn]

bladder: You're actually on to something there, I didn't think of that. But I'm not so sure if you're actually right in the way that the swap expression is undefined. The standard clearly says that such an expression can be undefined, but that is more in the general sense. The real question we need answered here is: is a compiler really allowed *in this particular case* to use old values of a and/or b high in the expression tree.

Surely, this is not undefined, at least not according to that paragraph:

a += b += 3;

both b and a are changed only once in the expression. Yet, how is that different when changing a to b. so it reads b += b += 3? If the compiler can choose the old value of b on the right side of the first +=, the first example would be undefined as well, which isn't the case.

But, when rambling about this, something came up. It may very well have to do with the actual storage of the result in the variables. So suppose we have this code

int b = 1;
b += b += 2;

Of course, you'd expect b to be increased to 3, and then add the result (3) to the new value of b (3), which results in 6.
Now let's assume some intermediate code the compiler produces with this expression

int b = 1;
register reg_b = b + 2;
b = reg_b; // #1
register reg_b2 = reg_b + reg_b;
b = reg_b2; // #2

Now, almost every compiler would ignore #1 here, but the standard doesn't say that it has to, nor does it say that it should come before #2. Clearly, when #1 is generated after #2, b would finally yield 3 instead of the 6 you suspect. I think this is where the 'undefinedness' (is that a word? it is now) comes from.

So yeah, that swap expression is probably undefined. Not in the way that it calculates the wrong value, but in the way that the actual calculated value is not returned to the variables correctly

I was wrong, every point their finger at me
COMMENCE FINGER-POINTING

[Kieran Hewitson]

sorry for the necro... but this post is quite high on google when searching swap variables...

FarooqMela said:

I had something similar sitting around in a header file...
Mine is one line of code though ;-)

inline void
UselessSwap(int& a, int &B)
{
  a -= b += a -= b = -b;
}

for me, that didn't work... but this did

a = 5;
b = 10;
b = (a += b -= a) - b;

I'm using C# not C++ so that might make a difference, i don't know.

There's actually 3 more ways of doing this as far as i know:

a ^= b;
b ^= a;
a ^= b;

the use of a 3rd variable also, and the obvious one:

b -= a;
a += b;
b = a - b;

hopefully those will help someone, if not then just kick me up the backside!

edit:
also, you can do this if you really want...

string aa = a.ToString();
string bb = b.ToString();
bb += aa;
aa = bb.Substring(0, bb.LastIndexOf(aa));
bb = bb.Replace(aa, "");
a = int.Parse(aa);
b = int.Parse(bb);

this will work for strings too, or pretty much anything provided it's got a way to convert to it's original format (maybe even your own custom class?)

but that's just me trying to be clever, if you had 2 classes that needed switching, it's best to use the a ^= b etc.

[rouncer]

you sort three variables using 3 swaps

if(a<b) swap(a,b);
if(b<c) swap(b,c);
if(a<b) swap(a,b);

thats what i use swapping lots for, and i also swap to get bounding
rects.

"It is important to swap."

But until I read this, i didnt know there were even fancier ways to do it. :)

[fireside]

Interesting read, but I won't remember any of them when I need to do it, so it's still old temp for me.

[Kieran Hewitson]

rouncer said:

if(a< swap(a,;
if(b<c) swap(b,c);
if(a< swap(a,;

aye but the way you sort is assuming you only have 3 numbers to sort .

I would use something more like this:

//Create List where you want, don't declare it publically though ;)
List<int> numbers = new List<int>{/*put your integers here in form 1,2,3*/};
numbers = Sort(numbers);

private List<int> Sort(List<int> numbers)
{
    //Declare new list to put the new sorted list into
    List<int> sortedNumbers = new List<int>();
    int i = 0;
    int imax = numbers.Count;
    for(i=0; i<imax;i++)
    {//Just a for, being done the amount of times as the amount of numbers in list
        int highest = Highest(numbers);
        sortedNumbers.Add(highest);
        numbers.Remove(highest);
    }

    return sortedNumbers;
}

private int Highest(List<int> numbers)
{//retrieves highest number to be removed from numbers and to be added to sortedList
    int highest = int.MinValue;
    foreach (var i in numbers)
    {
        if (i > highest)
            highest = i;
    }
    return highest;
}

This method doesn't call the sort more than needed... yours is what would be called the bubble sorting method, which would only work if you know exactly how many ints you are sorting and then you would need to change your code to look a mess. Using this method has compatibility for any size of list .

Is that 'swap' function built into a different code than c# or is it a function you made?

[Hickeroar]

thought of this in PHP this morning:

function swapVars (&$a, &$B) {
    list($b, $a) = array($a, $B);
}

[Reedbeta]

Actually, that uses temporaries internally, since you're constructing the array object and storing the values in it.

The Python "a,b = b,a" is the same way.

[Hickeroar]

Reedbeta said:

Actually, that uses temporaries internally, since you're constructing the array object and storing the values in it.

The Python "a,b = b,a" is the same way.

Yeah, it's definitely not a pure/academic answer. It's also probably not nearly as fast as the simple arithmetic solution.

The python method is what made me think of the "php alternative."

However, it's important to note that the python and php solutions would swap any variable type, whereas the arithmetic solutions only work on numbers.

Does anyone have any "true" solutions to this problem if you were operating on any given object, or string?

[Reedbeta]

You could apply one of the integer swap methods to every byte or word in an arbitrarily large chunk of data. (It would have to be a method that wasn't sensitive to overflow issues, e.g. the XOR one someone posted - I'm not sure if the add/subtract ones would work.) That should get you a bit-for-bit swap of the objects' memory images.

Of course, that's not always what you want when relocating objects...for instance if either object contains a pointer into itself, or a pointer to the other object, those would be wrong following the swap. (The same issues exist when swapping by means of a temporary copy, of course.)