欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数值直接交换及原理解释

程序员文章站 2022-07-13 09:08:55
...

问题:

如果实现两个数值直接交换,不使用第三个临时数值存储。

实现:

这个答案比较常见了,就是用异或实现源码如下,本文解释下其原理:

void exchange(int a, int b)
{
	print(a,b);
	a=a^b;
	b=a^b;
	a=a^b;
	print(a,b);
}

原理解析:

由于异或有两个不言自明的特性:

  1. A \bigoplus A = 0
  2. A \bigoplus B = B \bigoplus A

第一点:是由于异或自己的计算规则,只有两个对应二进制位的值不一致时,该值才为1,否则为0,自己跟自己的二进制所有位置的值完全一致,因此为0;
第二点:数据转换为二进制后,交换后不影响二进制的值,因此满足。

由前两点,可以推出:
A ⨁ B ⨁ A = B
推理过程如下:
A ⨁ B ⨁ A =
(A ⨁ B) ⨁ A =
(B ⨁ A) ⨁ A =
B ⨁ (A ⨁ A) =
B

代码解析

  1. a = a^b
    a保存a和b的异或值,即 a = a ⨁ b
  2. b = a^b
    ab的异或值和b,计算得到a,即b = (a ⨁ b) ⨁ b,此时等号右侧等于a,即 a = (a ⨁ b) ⨁ b,相当于已经完成了将a赋值给b,即b =a的操作。
  3. a = a^b
    a 通过ab的异或值,计算得到,即a = (a ⨁ b) ⨁ b,此时的b等于原来多a,因此相当于a = (a ⨁ b) ⨁ a,此时等号右侧等于b,即 b=(a ⨁ b) ⨁ a,相当于已经将a赋值给b。
相关标签: 个人杂谈 算法