Java算法 异或^运算（找重复，交换值）

一、异或运算
1、异或（^）运算说明
当对两个二进制位进行比较：如果两个位相同，则结果为0；如果两个位不同，则结果为1。
当对两个布尔表达式运算时，两个结果不同（一个true，一个false），返回true；两个结果相同（同为true，同为false），返回false

2、特点：
任何数和0做异或运算，结果仍然是原来的数，即a ^ 0 = a。
任何数和其自身做异或运算，结果是0，即a ^ a = 0。
异或运算满足交换律和结合律，即a ^ b ^ a = b ^ a ^ a = b ^ (a ^ a) = b ^ 0 = b。

3、基本示例
int a = 5; // 二进制表示: 0101
int b = 3; // 二进制表示: 0011
int result = a ^ b; // 异或操作
System.out.println("异或结果: " + result); // 输出: 6，二进制表示: 0110

二、算法示例
1、题目：0-999的数组中，添加一个重复的元素，打乱后，找出这个重复元素

import java.util.*;

public class XorTest {

    public static void main(String[] args) {
        // 生成一个0-1000的数组，之后对下标为1000下标元素的值重新生成重复的值
        Integer[] arr = new Integer[1001];
        for (int x = 0; x < arr.length; x++) {
            arr[x] = x;
        }
        Random r = new Random();
        arr[1000] = r.nextInt(1000);   // 0-999的随机数
        System.out.println("生成的随机数是:" + arr[1000]);

        // 顺序打乱
        List<Integer> arrList = new ArrayList<>();
        arrList.addAll(Arrays.asList(arr));
        Collections.shuffle(arrList);
        arr = arrList.toArray(new Integer[0]);

		// 基础双层循环比较算法
        basicMethod(arr);
        // 异或算法
        xorMethod(arr);
    }

    // 基础循环比较算法
    private static void basicMethod(Integer[] arr) {
        long startTime = System.nanoTime();
        int result = -1;
        itcast:
        for (int x = 0; x < arr.length; x++) {
            for (int y = x + 1; y < arr.length; y++) {
                if (arr[x].intValue() == arr[y].intValue()) {
                    result = arr[x];
                    break itcast;
                }
            }
        }
        System.out.println("这个重复的元素是：" + result);
        long endTime = System.nanoTime();
        System.out.println("基础算法共耗时：" + (endTime - startTime) + "纳秒");
    }

    // 异或算法
    private static void xorMethod(Integer[] arr) {
        long startTime = System.nanoTime();
        // 异或运算符改进
        for (int x = 1; x < arr.length; x++) {
            arr[0] ^= arr[x];
        }
        for (int x = 0; x < 1000; x++) {
            arr[0] ^= x;
        }
        System.out.println("这个重复的元素是：" + arr[0]);
        long endTime = System.nanoTime();
        System.out.println("异或共耗时：" + (endTime - startTime) + "纳秒");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

代码如上所示，我们看下运行的结果：

结果看出，两种方法都正确得到了重复的元素值。基础算法用时间是7位数的纳秒值，异或算法用的时间是6位数的纳秒值。可以看出异或运算的效率要高很多。
1秒 = 1000 * 1000 * 1000纳秒 （秒，毫秒，微秒，纳秒）
说明：
异或算法正是结合了a ^ 0 = a，a ^ a = 0的特点以及异或运算满足交换律特点。
原理：先将带有重复的数组全部异或一遍，之后在和之前非重复的数组全部异或一遍。此时，非重复的元素之间都异或一次后得到的结果为0，重复值异或了2次又得到了数据本身，所以就找出了重复值。

2、题目：交换两个数字值

package com.zw.study.algorithm;

public class XorTest1 {

    public static void main(String[] args) {
        basicMethod();
        xorMethod();
    }

    // 基础算法，第三方变量
    private static void basicMethod() {
        long startTime = System.nanoTime();
        for (int x = 0; x < 1000; x++) {
            int a = 10;
        	int b = 20;
            int temp = a;
            a = b;
            b = temp;
            if (x == 0) {
                System.out.println("常规转顺序:" + a + "," + b);
            }
        }
        long endTime = System.nanoTime();
        System.out.println("常规算1000次共耗时：" + (endTime - startTime) + "纳秒");
    }

    // 异或算法
    private static void xorMethod() {
        long startTime = System.nanoTime();
        for (int x = 0; x < 1000; x++) {
        	int a = 10;
        	int b = 20;
            a = a ^ b; // a = a ^ b
            b = a ^ b; // b = a ^ b = a ^ b ^ b = a;
            a = a ^ b; // a = a ^ b = a ^ b ^ a = b;
            if (x == 0) {
                System.out.println("异或转顺序:" + a + "," + b);
            }
        }
        long endTime = System.nanoTime();
        System.out.println("异或算1000次共耗时：" + (endTime - startTime) + "纳秒");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

运行上面代码结果如下：

可以看出都能正确交换数据的值，异或的运算耗时相对第三个变量而言，既节省时间，也节省空间，当属于更优的算法。
说明：
左侧a,b为赋值，a1和b1为最初的a和b的值
第一次a = a ^ b; // a为a1^b1,b为b1
第二次b = a ^ b; // b = a ^ b = a1 ^ b1 ^ b1 = a1; 即b为最初a的值
第三次a = a ^ b; // a = a ^ b = a1 ^ b1 ^ a1 = b1; 即a为最初b的值

学海无涯苦作舟！！！