交换两个变量的值,不使用第三个变量的几种方法

2018/02/20 面试

题目

题目:已知两变量a和b,设计一个算法,交换a与b的值。

原始方法

1、最传统,最广泛,最著名的方法,增加一个变量,代码如下:

int a, b;
int c;
c=a;
a=b;
b=c;

不引入变量的方法

2、不增加第三个变量,交换a和b的值

2.1、 方法一:加减运算

int a, b;
a = a+b;
b = a-b;
a=a-b;

分析,设a和b的原始值为 a,b。

执行代码 变量a 变量b
int a, b a b
a = a+b a+b b
b = a-b a+b a+b-b = a
a = a-b a+b-(b) = a+b-a = b a

2.2、 方法二:异或运算

异或运算符 ^ 也称 XOR 运算符,它的规则是若参加运算的两个二进位同号,则结果为0(假);异号为1(真)。即 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0

int a, b;
a = a^b;
b = a^b;
a = a^b;

分析,前两个赋值语句:a = a ^ b;b = b ^ a; 相当于 b = b ^ (a ^ b),而 b ^ a ^ b 等于 a ^ b ^ bb ^ b 的结果为0,因为同一个数与相同的数相 ^ ,结果必为 0。因此b的值等于 a ^ 0,即 a
再执行第三个赋值语句:a = a ^ b。由于 a 的值等于 (a ^ b)b 的值等于 (b ^ a ^ b),因此,相当于 a = a ^ b ^ b ^ a ^ b ,即 a 的值等于 a ^ a ^ b ^ b ^ b ,等于 b

或者用列表方式分析。设 a 和 b 的原始值为 a1,b1。

目标 操作 操作后状态
a = a1 ^ b1 a = a ^ b a = a1 ^ b1, b = b1
b = a1 ^ b1 ^ b1 b = a ^ b a = a1 ^ b1, b = a1
a = b1 ^ a1 ^ a1 a = a ^ b a = b1, b = a1

注意

问题:用加减运算的时候要注意不要溢出,用异或运算的时候,不要两个相同的数进行交换。

参考

CSDN-不引入第三变量,交换两个变量的值


知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Search

    Table of Contents