суббота, 10 сентября 2011 г.

Solution to XOR Variable Swapping

So you have two variables, a and b; we'll assign a to be 5, and b to be 10. We want to store the value of a in b, and the value of b in a, but without using a temporary variable.
int a, b;
a = 5;
b = 10;

We can do this using bitwise XOR remembering the principle that two applications of XOR to a variable will "cancel out". Here's a function that will take pointers to two variables and flip them. For clarity, I'll refer to the original values stored in a and b as a_orig and b_orig. Originally, *a and *b will be a_orig and b_orig, but this will change over time.
void flip(int *a, int *b)
    *a = *a ^ *b;
    // Now, we can recover *a_orig by applying *a XOR *b_orig
    *b = *a ^ *b;
    // So we have the following situation:
    // The value originally stored in *a, a_orig, is now in *b
    // and *a still stores a_orig ^ b_orig
    // This means that we can recover the value of b_orig by applying 
    // the XOR operation to *a and a_orig.  Since *b stores a_orig...
    *a = *a ^ *b

Памятка себе. Источник: http://www.cprogramming.com/tutorial/xorsol.html

a ^= b ^= a ^= b;

Источник: http://graphics.stanford.edu/~seander/bithacks.html

Комментариев нет:

Отправить комментарий