交换两个变量值而不使用第三个变量 [英] Swapping two variable value without using third variable

问题描述

面试中提出的一个非常棘手的问题。

One of the very tricky questions asked in an interview.

交换两个变量的值，例如 a = 10 和 b = 15 。

Swap the values of two variables like a=10 and b=15.

通常要交换两个变量值，我们需要第三个变量，如：

Generally to swap two variables values, we need 3rd variable like:

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

现在要求是，不使用第3个变量就交换两个变量的值。

Now the requirement is, swap values of two variables without using 3rd variable.

推荐答案

使用异或交换算法

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上的所有其他异或运算将等于0（因为它们相同），这意味着该函数会将* x和* y都设置为0。

The test is to ensure that x and y have different memory locations (rather than different values). This is because (p xor p) = 0 and if both x and y share the same memory location, when one is set to 0, both are set to 0. When both *x and *y are 0, all other xor operations on *x and *y will equal 0 (as they are the same), which means that the function will set both *x and *y set to 0.

如果它们具有相同的值但存储位置不同，那么一切都会按预期工作

If they have the same values but not the same memory location, everything works as expected

*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

应该

在一般情况下，不会。编译器将优化临时变量，并考虑到交换是一个常见过程，它应为您的平台输出最佳机器代码。

In general cases, no. The compiler will optimize away the temporary variable and given that swapping is a common procedure it should output the optimum machine code for your platform.

例如，编写了此快速测试程序

Take for example this quick test program written in 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

异或版本

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

带临时变量的版本取值：

Where as the version with the temporary variable takes:

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

这篇关于交换两个变量值而不使用第三个变量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！