Adrian Lita

Swapping numbers without the third variable

by Adrian Lita - on 2018-06-12

Keywords: #swapping #variables #academic #snippet #xorswap #xor
Permalink: https://adrian.lita.me/blog_swapping-numbers-without-the-need-of-third-variable-c.html
 

While not recommeded to be used in modern programming, this simple method allows swapping the values of 2 variables without the need of the third.

Some caution should be taken into consideration, because this method works as long as both the variables that needed to be swapped are different (read: occupy different memory).

void xorSwap(int *a, int *b)
{
  *a = *a ^ *b;
  *b = *b ^ *a;
  *a = *a ^ *b;
}

This is the simplest variant of the xorSwap. Several other improvements might be done to it. One would be to check the actual pointers that they're different:

void xorSwap(int *a, int *b)
{
  if(a != b)
  {
    *a = *a ^ *b;
    *b = *b ^ *a;
    *a = *a ^ *b;
  }
}

However, since the first variant is as fast as an actual swap using the 3rd variable (3 instructions), it can be used with caution. The main reason the use of this is not recommended is because the compiler knows how to optimize swaps by itself (not always with xorSwap), without the need of user intervention.

Going further on the academic path, and given that the memory itself is made by bytes, an actual function that can swap any variable can be implemented:

void xorSwapAnything(const int n, void *a, void *b)
{
	for (int i = 0; i < n; i++)
	{
		((unsigned char*)a)[i] = ((unsigned char*)a)[i] ^ ((unsigned char*)b)[i];
		((unsigned char*)b)[i] = ((unsigned char*)b)[i] ^ ((unsigned char*)a)[i];
		((unsigned char*)a)[i] = ((unsigned char*)a)[i] ^ ((unsigned char*)b)[i];
	}
}

int main()
{
	//just for testing
	struct {
		int a;
		int b;
		int c;
	} x, y;

	x.a = 1;
	x.b = -1;
	x.c = 2;

	y.a = 100;
	y.b = -100;
	y.c = 123456;

	xorSwapAnything(sizeof(x), &x, &y);

	return 0;
}