Difficulty: ★ ★ ★ ☆
Swapping values is common task in computer programming, often used when sorting. You need the value of variable a
in variable b
and vice-versa. A number of methods are available for swapping, most of which involve using a temporary variable to hold one of the values during the swap.
I can think of two instances where a temporary variable isn’t required.
The first I wrote about a while back, where a third variable isn’t needed when swapping two integer values. Here’s the clever approach:
b = b + a;
a = b - a;
b = b - a;
The second method I use often in Assembly language: Push two values on the stack and then pop them off in reverse order. For example:
push ax
push bx
pop ax
pop bx
A third variable isn’t required here. The stack is used as storage where values are pushed and then removed. Very nerdy.
For this month’s Exercise, your task is to swap the values of two variables. Yes, you can use a “temp” variable or swap the two values any way you like. The restriction is that the swapping takes place in a function. This skeleton below may give you an idea of what I’m after.
2024_01_01-Lesson.c
#include <stdio.h>
int main() {
int x = 5;
int y = 10;
printf("Before swap: x=%d, y=%d\n",x,y);
/* swap function call here */
printf("After swap: x=%d, y=%d\n",x,y);
return 0;
}
Your task is to write the swap() function. It’s set in the code where the comment appears above. Yes, the limitation here is that functions in C return only a single value. Part of the challenge is how to work out this conundrum.
Please give this Exercise a try before you view my solution.
#include <stdio.h>
void swapints(int*, int*);
int main()
{
int x = 5;
int y = 10;
printf(“Before swap: x=%d, y=%d\n”, x, y);
swapints(&x, &y);
printf(“After swap: x=%d, y=%d\n”, x, y);
return 0;
}
void swapints(int* px, int* py)
{
*py = *py + *px;
*px = *py – *px;
*py = *py – *px;
}
Just to prove itʼs possible to do in a one-liner:
void swap (int *a, int *b) {
*b = *a + *b – (*a = *b);
}
⋮
swap (&x, &y); /* swap function call here */
As addition/subtraction has left-to-right associativity (the parenthesis being necessary necessary because assignment has lower precedence), the above should force the compiler to perform *a + b* (in a temporary/register) before attempting (*a = *b) [followed by a final subtraction].
Regrettably, the involved trickery is kind of an intelligence test for compilers that older ones donʼt necessarily pass—to wit, hereʼs what Visual Studio 2008 produces for the above source code:
void swap (int *a: RCX, int *b: RDX) {
mov RAX, dword ptr [RDX]
mov dword ptr [RCX], RAX
}
⋮
lea RDX,[y] ; RDX = &y
lea RCX,[x] ; RCX = &x
call swap
That’s not quite what was intended… as Compiler Explorer demonstrates, GCC with -O2 gets it though:
void swap (int *a: RDI, int *b: RSI) {
mov EAX, dword ptr [RDI]
mov EDX, dword ptr [RSI]
mov dword ptr [RDI], EDX
mov dword ptr [RSI], EAX
}
⋮
; See “registers for parameter transfer” in Agner Fogʼs calling_conventions.pdf:
lea RSI,[y] ; RSI = &y
lea RDI,[x] ; RDI = &x
call swap
If it counts, I’d prefer Chris Webbʼs solution—the above is likely too much hit and miss with different compilers.
A bit of bitwise arithmetic here 🙂
#include
void swap_xor( int *x, int *y );
int main( void ) {
int x = 5;
int y = 10;
printf( “Before swap: x = %d, y = %d\n”, x, y );
swap_xor( &x, &y );
printf( “After swap: x = %d, y = %d\n”, x, y );
return 0;
}
void swap_xor( int *x, int *y ) {
*x = *x ^ *y;
*y = *x ^ *y;
*x = *x ^ *y;
}