在不使用第三个variables的情况下交换两个variables值
其中一个非常棘手的问题在采访中被问到。
交换两个variables的值，如a=10和b=15 。
通常交换两个variables值，我们需要第三个variables，如：
temp=a; a=b; b=temp;
现在要求是，不使用第三个variables交换两个variables的值。
使用xor交换algorithm
void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different *x ^= *y; *y ^= *x; *x ^= *y; } }
为什么要testing？
testing是为了确保x和y有不同的内存位置（而不是不同的值）。 这是因为(p xor p) = 0 ，如果x和y共享相同的内存位置，当一个设置为0时，两者都设置为0.当* x和* y都为0时，所有其他异或运算* x和* y将等于0（因为它们是相同的），这意味着该函数将把* x和* y设置为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
这是否应该使用？
在一般情况下，没有。 编译器会优化临时variables，并且假定交换是一个普通的过程，它应该为您的平台输出最佳的机器代码。
以C语言编写的这个快速testing程序为例
#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
作为临时variables的版本需要：
real 0m0.543s user 0m0.540s sys 0m0.000s
一般forms是：
A = A operation B B = A inverse-operation B A = A inverse-operation B
但是您必须注意溢出，并且并不是所有的操作都有相反的定义。 例如*和/工作，直到A或B为0
xor是特别令人满意的，因为它被定义为所有的整数并且是它自己的逆
a = a + b b = a - b // b = a a = a - b
没有人build议使用std::swap 。
std::swap(a, b);
我不使用任何临时variables，取决于a和b的types，实现可能有一个规范化，但不是。 执行应该被写入知道一个“技巧”是否合适。 试图猜测是没有意义的。
更一般地说，我可能想要做这样的事情，因为它可以用于typestypes，使得ADL在可能的情况下find更好的重载。
using std::swap; swap(a, b);
当然，面试官对这个答案的反应可能会对空缺说很多。
正如manu所指出的，XORalgorithm是一种stream行的algorithm，它适用于所有的整数值（包括指针，然后带有一些运气和铸造）。 为了完整起见，我想提一下加/减法的另一个较弱的algorithm：
A = A + B B = A - B A = A - B
在这里你必须小心溢出/下溢，但否则它的工作就好。 在这种情况下，你甚至可以在浮动/双打的情况下尝试XOR。
愚蠢的问题应该得到适当的答案：
void sw2ap(int& a, int& b) { register int temp = a; // ! a = b; b = temp; }
唯一的好用的关键字。
你看过XOR交换algorithm吗？
#include<iostream.h> #include<conio.h> void main() { int a,b; clrscr(); cout<<"\n==========Vikas=========="; cout<<"\n\nEnter the two no=:"; cin>>a>>b; cout<<"\na"<<a<<"\nb"<<b; a=a+b; b=ab; a=ab; cout<<"\n\na="<<a<<"\nb="<<b; getch(); }
由于原来的解决scheme是：
temp = x; y = x; x = temp;
你可以通过使用下面的内容来使它成为一个双线程
temp = x; y = y + temp -(x=y);
然后用下面的方法把它作为一个class轮：
x = x + y -(y=x);
这是一个更多的解决scheme，但一个风险。
码：
#include <iostream> #include <conio.h> void main() { int a =10 , b =45; *(&a+1 ) = a; a =b; b =*(&a +1); }
位置a + 1的任何值都将被覆盖。
如果你稍微改变一下问题而不是variables，那么你可以使用xchg操作作为一个选项，而堆栈操作也可以用作另一个选项。
考虑a=10 ， b=15 ：
使用加法和减法
a = a + b //a=25 b = a - b //b=10 a = a - b //a=15
使用除法和乘法
a = a * b //a=150 b = a / b //b=10 a = a / b //a=15
#include <stdio.h> int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); a ^= b; b ^= a; a ^= b; printf("\nValue of A=%d B=%d ",a,b); return 1; }
a = a + b - (b=a);
这很简单，但可能会提出警告。
这是正确的XOR交换algorithm
void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different if (*x != *y) { //ensure that values are different *x ^= *y; *y ^= *x; *x ^= *y; } } }
您必须确保内存位置不同，并且实际值也不同，因为A XOR A = 0
你可以用简单的方法……在一行内逻辑
#include <stdio.h> int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a^b^(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; }
要么
#include <stdio.h> int main() { int a, b; printf("Enter A :"); scanf("%d",&a); printf("Enter B :"); scanf("%d",&b); int a = 1,b = 2; a=a+b-(b=a); printf("\nValue of A=%d B=%d ",a,b); return 1; }
public void swapnumber(int a,int b){ a = a+b-(b=a); System.out.println("a = "+a +" b= "+b); }
#include <iostream> using namespace std; int main(void) { int a,b; cout<<"Enter a integer" <<endl; cin>>a; cout<<"\n Enter b integer"<<endl; cin>>b; a = a^b; b = a^b; a = a^b; cout<<" a= "<<a <<" b="<<b<<endl; return 0; }
更新：在这个我们正在从用户input两个整数。 然后我们使用按位XOR操作来交换它们。
假设我们有两个整数a=4和b=9然后：
a=a^b --> 13=4^9 b=a^b --> 4=13^9 a=a^b --> 9=13^9
让我们来看一个简单的例子来交换两个数字而不使用第三个variables。
程序1：
#include<stdio.h> #include<conio.h> main() { int a=10, b=20; clrscr(); printf("Before swap a=%db=%d",a,b); a=a+b;//a=30 (10+20) b=ab;//b=10 (30-20) a=ab;//a=20 (30-10) printf("\nAfter swap a=%db=%d",a,b); getch(); }
输出：
交换前a = 10 b = 20交换后a = 20 b = 10
程序2：使用*和/
我们来看另一个例子，用*和/来交换两个数字。
#include<stdio.h> #include<conio.h> main() { int a=10, b=20; clrscr(); printf("Before swap a=%db=%d",a,b); a=a*b;//a=200 (10*20) b=a/b;//b=10 (200/20) a=a/b;//a=20 (200/10) printf("\nAfter swap a=%db=%d",a,b); getch(); }
输出：
交换前a = 10 b = 20交换后a = 20 b = 10
程序3：利用按位异或运算符：
按位XOR运算符可用于交换两个variables。 两个数字x和y的XOR返回一个数字，它的所有位都是1，无论x和y的位有什么不同。 例如10（二进制1010）和5（二进制0101）的XOR是1111，7（0111）和5（0101）的XOR是（0010）。
#include <stdio.h> int main() { int x = 10, y = 5; // Code to swap 'x' (1010) and 'y' (0101) x = x ^ y; // x now becomes 15 (1111) y = x ^ y; // y becomes 10 (1010) x = x ^ y; // x becomes 5 (0101) printf("After Swapping: x = %d, y = %d", x, y); return 0;
输出：
交换之后：x = 5，y = 10
计划4：
没有人build议使用std :: swap。
std::swap(a, b);
我不使用任何临时variables，取决于a和b的types，实现可能有一个规范化，但不是。 执行应该被写入知道一个“技巧”是否合适。
以上方法的问题：
1）如果其中一个数字为0，则产品变为0，而不考虑其他数字，则基于乘法和除法的方法不起作用。
2）两种算术解决scheme都可能导致算术溢出。 如果x和y太大，则加法和乘法可能超出整数范围。
3）当我们使用指向variables的指针并进行函数交换时，当两个指针指向同一个variables时，上述所有方法都会失败。 让我们来看看在这种情况下，如果两者都指向相同的variables会发生什么。
//基于位的XOR方法
x = x ^ x; // x becomes 0 x = x ^ x; // x remains 0 x = x ^ x; // x remains 0
//基于算术的方法
x = x + x; // x becomes 2x x = x – x; // x becomes 0 x = x – x; // x remains 0
让我们看看下面的程序。
#include <stdio.h> void swap(int *xp, int *yp) { *xp = *xp ^ *yp; *yp = *xp ^ *yp; *xp = *xp ^ *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; }
输出 ：
交换后（＆x，＆x）：x = 0
在许多标准algorithm中可能需要交换一个variables。 例如，参见QuickSort的这个实现，我们可以在其中交换一个variables。 上述问题可以通过在交换之前添加条件来避免。
#include <stdio.h> void swap(int *xp, int *yp) { if (xp == yp) // Check if the two addresses are same return; *xp = *xp + *yp; *yp = *xp - *yp; *xp = *xp - *yp; } int main() { int x = 10; swap(&x, &x); printf("After swap(&x, &x): x = %d", x); return 0; }
输出 ：
交换（＆x，＆x）后：x = 10
最好的答案是使用XOR并在一行中使用它会很酷。
(x ^= y), (y ^= x), (x ^= y);
x，y是variables，它们之间的逗号引入了序列点，所以它不会依赖于编译器。 干杯!
用c语言交换两个值的单行解决scheme。
a=(b=(a=a+b,ab),ab);
second_value -= first_value; first_value += second_value; second_value -= first_value; second_value *= -1;
