【程序员代码面试指南】不用额外变量交换两个整数的值

题目描述

• 如何不用额外变量交换两个整数的值？
• 输入描述：输出一行，包含两个整数n和m(-10^9<=n,m<=10^9)。输入：2 3
• 输出描述：输出交换后的n和m值。输出：3 2
• 备注：时间复杂度O(1)，额外空间复杂度O(1)。
• 考点：位运算

解题思路

一般情况下，交换两个数值首先考虑的是申请一个额外变量。如若不用额外变量，则需要考虑异或运算，例如已知整数a = 4（0100）和b = 3（0011）：第一步，将a（0100）与b（0011）异或（位相同异或值是0，位不同异或值是1）可得a与b的位差异值7（0111），赋值于a；第二步，将a（0111）与b（0011）异或可得4（0100），赋值于b，此时b = 4；第三步，将a（0111）与b（0100）异或可得3（0011），赋值于a，此时a = 3。两个整数在不借助任何额外变量情况下成功交换。

Java (javac 1.8)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);  // 输入
        while (input.hasNext()) {
            int n = input.nextInt();  // 输入整数n
            int m = input.nextInt();  // 输入整数m
            n = n ^ m;  // n与m异或，此时n值是n与m的位差异值
            m = n ^ m;  // n与m异或，此时m值是原先整数n的值
            n = n ^ m;  // n与m异或，此时n值是原先整数m的值
            System.out.println(n + " " + m);  // 依次输出交换后的整数n和整数m
        }
    }
}