65.9K
CodeProject is changing. Read more.
Home

The Stupid XOR Trick

starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.58/5 (28 votes)

Aug 14, 2002

CPOL

2 min read

viewsIcon

261983

Explaining the phenomenon of x^=y^=x^=y;

Introduction

As a result of many, sometimes insulting, reactions on my signature, I decided to write an article on this topic. The mentioned signature looks like this:

int x=1, y=5; 
x^=y^=x^=y; // what's the content of x and y now?

Well, the reactions range from "that's not even valid C/C++ code" to "that works only with X=1 and y=5" and "you better learn C". To all these unbelievers and of course everyone else who doesn't know this "trick"; may this article enlighten you :)

What it's meant to do

Simply exchange the values of two integer variables without using a temporary variable. It gives unpredictable results with other variable types than integer types.

The symbol ^ is the XOR operator used in C/C++. See the article from PJ Arends on Bitwise Operators for a full introduction to bits and related operators.

The questionable code fragment x^=y^=x^=y; can be expanded into x XOR y XOR x XOR y. Since C/C++ resolves expressions like this from right to left, we can split it into the steps performed by the compiler:

x ^= y; // the right-most expression
y ^= x; // the middle expression
x ^= y; // the left-most expression

Which can be further expanded into

x = x ^ y; // x = 1 XOR 5  -> x = 4
y = y ^ x; // y = 5 XOR 4 = 1  -> y = 1
x = x ^ y; // x = 4 XOR 1 = 5  -> x = 5

Voila, here we are x=5 and y=1. That's what we wanted to achieve. And all this without using a temporary variable like in int t = x; x = y; y = t; which most programmers use. I confess that my method is confusing to most people because it's a little known method. As an additional benefit, the compiler can translate it into 3 simple XOR assembler statements.

Sample

For all who still don't believe it, here is a sample program to prove  that it works (with any integer number). The sample can be compiled in Ansi and Unicode and is compatible with VC6 and VC7. It is not using any library except the standard C Runtime Library.

#include <stdio.h>
#include <stdlib.h>
#include <tchar.h>

int _tmain(int argc, TCHAR* argv[])
{
    if(argc != 3)
    {
        _tprintf(
            _T("\nUsage: StupidXORTricks.exe intvalue1 intvalue2\n"));
    }
    else
    {
        int x = _ttoi(argv[1]);
        int y = _ttoi(argv[2]);

        _tprintf(_T("x = %d, y = %d\n"), x, y);
        _tprintf(_T("Performing x^=y^=x^=y...\n"));
		
        x^=y^=x^=y;

        _tprintf(_T("x = %d, y = %d\n"), x, y);

    }
    return 0;
}

Finally, I hope that I don't get any more responses to my sig. :)