Swapping 3 integers in C program

[kthouz]

Hi! i have a problem about swapping three integers in C program.
Usually i use the call by reference for two integers only. Now for three i can't get t.

 

[Math Is Hard]

I usually create a temporary variable to hold a value while I am doing a swap. Would that do the trick?

 

[rcgldr]

Or the old fashion way, more instructions but no temp variable for a swap:

A ^= B
B ^= A
A ^= B

A 3 variable swap is really a rotate.

T = A
A = B
B = C
C = T

 

[tabchouri]

To swap 3 integer consider the following 2 methods:

* divide to conquer: swap 2 by 2
swap A & B
A = B+A
B = A-B
A = A-B

then swap A & C or B & C

* all in one:
let the variables A, B & C have the initial values A0,B0 & C0 respectively
A = A+B+C (A0+B0+C0)
B = A-B-C (A0+B0+C0 - B0 - C0 = A0)
C = A-B-C (A0+B0+C0 - A0 - C0 = B0)
A = A-B-C (A0+B0+C0 - A0 - B0 = C0)

-----------------------------------------------------
Correct me if I am wrong.
http://ghazi.bousselmi.googlepages.com/présentation2

 

[kthouz]

thanks but i can't really get it!
i was expeting of having at least 5lines. (because number of possible swaps=n!)
indeed we are preparing our exam,the teacher didn't explain it clearly and he just told us to figure it out ourselves. please gimme an full example so that i can see the whole format.

 

[rcgldr]

All possible swaps? There are 6 ways you can order 3 variables.

A B C // no swaps
A C B // swapsecondpair
B A C // swapfirstpair
B C A // swapfirstpair, swapsecondpair
C A B // swapouterpair, swapsecondpair
C B A // swapouterpair

int A, B, C, T;

void swapfirstpair()
{
    T = A;
    A = B;
    A = T;
}

void swapsecondpair()
{
    T = B;
    B = C;
    C = T;
}

void swapouterpair()
{
    T = A
    A = C
    C = T
}

 

[Jheriko]

To swap 3 integer consider the following 2 methods:

* divide to conquer: swap 2 by 2
swap A & B
A = B+A
B = A-B
A = A-B

then swap A & C or B & C

* all in one:
let the variables A, B & C have the initial values A0,B0 & C0 respectively
A = A+B+C (A0+B0+C0)
B = A-B-C (A0+B0+C0 - B0 - C0 = A0)
C = A-B-C (A0+B0+C0 - A0 - C0 = B0)
A = A-B-C (A0+B0+C0 - A0 - B0 = C0)

-----------------------------------------------------
Correct me if I am wrong.
http://ghazi.bousselmi.googlepages.com/présentation2

you can do this more efficiently and without rounding errors by using ^ to the same effect

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

swap the variable names to change the swapping that is performed, you can extend this to n variables afaik... this works because ^ preserves information in the same way as + and -, except that because the operation is its own inverse there is one symbol instead of two, also because it is bitwise there is no precision loss.

 

[mattst88]

I can't believe people are recommending the triple xor trick. Yes it is clever, but it's pretty bad to use it in a language even as high level as C.

Compiling your code with any optimization at all will cause the compiler to optimize out the temporary variable.

If you're really interested in using assembleresque tricks, you might as well check out Sean Andersen's Bit Twiddling Hacks.

 

[tabchouri]

you can do this more efficiently and without rounding errors by using ^ to the same effect

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

swap the variable names to change the swapping that is performed, you can extend this to n variables afaik... this works because ^ preserves information in the same way as + and -, except that because the operation is its own inverse there is one symbol instead of two, also because it is bitwise there is no precision loss.

with + and - there is no precision loss neither, there might be some cyclic overflows in the intermediate values, but the final results will always be correct.

-----------------------------------------------------
Correct me if I am wrong.
http://ghazi.bousselmi.googlepages.com/présentation2

 

[Hurkyl]

there might be some cyclic overflows in the intermediate values, but the final results will always be correct.

As I recall, the C standard says that (signed) integer overflow results in undefined behavior.

 

[CRGreathouse]

As I recall, the C standard says that (signed) integer overflow results in undefined behavior.

Probably. But if the computer uses IEEE arithmetic the overflow won't affect the result as tabchouri says. It would be best to comment this, but most modern systems use IEEE... yes?

 

[Hurkyl]

I thought IEEE only referred to floating point arithmetic? (In this context)

But yes, most systems will do what you expect it to do. But you shouldn't assume it -- for example, what if someone using some fancy system decides to enable trapping of arithmetic overflow, so as to detect errors? Or you're using some fancy OS that uses trap bits in its integer representations to detect a variety of errors?



I'm always amused by observations such as... signed integer overflow formatting your hard drive is permitted by the C standard.

 

[CRGreathouse]

I thought IEEE only referred to floating point arithmetic? (In this context)

Yeah, you're right of course... what is the name for the standard I'm thinking of?

I'm always amused by observations such as... signed integer overflow formatting your hard drive is permitted by the C standard.

Quite right, and amusing too. :D