[解決済み] 第3の変数を使用せずに2つの変数の値を入れ替える

質問

面接で聞かれる非常に難しい質問の1つです。

のような2つの変数の値を入れ替えて a=10 と b=15 .

一般に、2つの変数の値を入れ替えるには、3番目の変数が必要です。

temp=a;
a=b;
b=temp;

3番目の変数を使わずに、2つの変数の値を入れ替えることが必要です。

どのように解決するのですか？

を使用して xorスワップアルゴリズム

void xorSwap (int* x, int* y) {
    if (x != y) { //ensure that memory locations are different
       *x ^= *y;
       *y ^= *x;
       *x ^= *y;
    }
}

なぜテストなのですか？

このテストは、xとyが（異なる値ではなく）異なるメモリ位置を持っていることを確認するためのものです。これは (p xor p) = 0 で、x と y の両方が同じメモリ位置を共有している場合、一方が 0 に設定されると、両方が 0 に設定されます。 x と *y の両方が 0 の場合、*x と *y に対する他のすべての xor 演算は 0 になります（これらは同じであるため）。

それらが同じ値を持つが、同じメモリ位置でない場合、すべてが期待通りに動作する

*x = 0011
*y = 0011
//Note, x and y do not share an address. x != y

*x = *x xor *y  //*x = 0011 xor 0011
//So *x is 0000

*y = *x xor *y  //*y = 0000 xor 0011
//So *y is 0011

*x = *x xor *y  //*x = 0000 xor 0011
//So *x is 0011

これは使うべきですか？

一般的なケースでは、いいえ。コンパイラは一時変数を最適化し、スワップが一般的な手順であることを考慮し、プラットフォームに最適なマシンコードを出力するはずです。

例えば、C 言語で書かれたこの簡単なテスト プログラムを見てみましょう。

#include <stdlib.h>
#include <math.h>

#define USE_XOR 

void xorSwap(int* x, int *y){
    if ( x != y ){
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}

void tempSwap(int* x, int* y){
    int t;
    t = *y;
    *y = *x;
    *x = t;
}


int main(int argc, char* argv[]){
    int x = 4;
    int y = 5;
    int z = pow(2,28); 
    while ( z-- ){
#       ifdef USE_XOR
            xorSwap(&x,&y);
#       else
            tempSwap(&x, &y);
#       endif
    }
    return x + y;    
}

を使ってコンパイル。

gcc -Os main.c -o swap

xorバージョンは

real    0m2.068s
user    0m2.048s
sys  0m0.000s

ここで、一時的な変数があるバージョンが取るように。

real    0m0.543s
user    0m0.540s
sys  0m0.000s