java 中利用异或实现两个变量互换

时间:2022-04-28 15:55:25

一般实现两个变量之间的互换要用第三个变量,这样做可以,但创建新变量,增加了系统开销。如果要交换的变量时两个整数型变量,可以用更高效的方法。例如:^(异或)操作,举例如下:

package chapterOne;
import java.util.Scanner; public class VariableExchange { public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.println("Please enter first variable A:");
long A=scan.nextLong();
System.out.println("Please enter second variable B:");
long B=scan.nextLong();
System.out.println("A="+A+"\tB="+B);
System.out.println("Implementation of variable swap");
A=A^B;
System.out.println("A="+A+"\tB="+B);
B=B^A;
System.out.println("A="+A+"\tB="+B);
A=A^B;
System.out.println("A="+A+"\tB="+B);
} }

原理理解如下:

a-------------------------b
a^=b    a^b-----------------------b
b^=a    a^b-------b^(a^b) => a
a^=b    a^b^(a) => b-----------a

OK           b-------------------------a

要知道,a^b=c  =>  a^c=b;a^c=b;

即只要直到a,b,c中的任意两个,即可利用异或运算退出另外一个数。

RAID里面就用到了这技术。三个里面知道任意两个就可以恢复第三个,磁盘位的恢复的一种手段。

数学上的原理如下:

^ 在 C 里面是按位异或操作符。异或运算的原理应该清楚吧?相同的话异或的结果就是 0,不同的话就是 1。举个例子,比如 a 表示十进制的 5,b 表示十进制的 12,按位异或结果就是:

a = 0101   (5 的二进制表示)
b = 1100   (12 的二进制表示)
    ----
c = 1001   (结果为 9)

有两个定理:
任何一位二进制数同 1 异或都会变成另外一个(0 同 1 异或的结果是 1,1 同 1 异或的结果是 0)
任何一位二进制数同 0 异或都保持不变(0 同 0 异或的结果是 0,1 同 0 异或的结果是 1)

因为 c 中是 1 的部分表示 a 和 b 中按位不同的位,0 表示 a 和 b 中按位相同的位,那么 a 同 c 异或的结果就是 a 中与 b 不同的位发生变化,二进制数每位只有两种状态,所以 a 变成了 b:

a = 0101
c = 1001
    ----
b = 1100

同样, b 与 c 异或结果就变成了 a:

b = 1100
c = 1001
    ----
a = 0101