数据结构与算法拾遗九（异或运算）

认识异或运算

特点：
1、相同为0不同为1（二进制位上面看）
2、代表无进位相加
3、0^N = N
4、N^N = 0
5、异或运算满足交换律和结合律
a^b= b^a
(a^b) ^ c= a ^ (b ^ c)
如下证明：
在某一位上如果有偶数个1那么最后的结果为0
在某一位上如果有奇数个1那么最后的结果为1

如何不用任何额外变量交换两个数

异或运算的效率高于加减法：
如下代码逐行分析：
arr[i] = 甲
arr[j] = 乙
1）arr[i] = 甲 ^乙
2）arr[j] = 甲^乙 ^ 甲 = 乙
3）arr[j] = 甲 ^ 乙 ^ 乙 = 甲

//前提是 arr[i]和arr[j] 不能是同一个位置（不能共享同一个内存空间）会把自己变成0
//所以上游函数调用传入参数不能传两个一样的位置
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
1
2
3
4
5
6
7

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

思路：通过异或遍历一遍只用一个变量

	// arr中，只有一种数，出现奇数次
	public static void printOddTimesNum1(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		System.out.println(eor);
	}

1
2
3
4
5
6
7
8
9

怎么把一个int类型的数，提取出最右侧的1

a = 01101110010000
&
//~a = 10010001101111(相当于先打散最右侧的1，然后再通过+1合并回来原来的1)
~a +1 = 10010001110000
ans = 00000000010000
如上a&(~a+1) = a&(-a);

一个数组中有两种数出现了奇数次，其他数出现了偶数次，怎么找到并打印这两种数

首先知道eor！=0，然后找到最右侧的1，假设是在第x位，说明a的x位和b的x位肯定不同，找到数组中第x位为1和第x位为0的数。
数组中第x位为1的和第x位为0的数都是互斥的（无论出现是奇数次还是偶数次）
这里再定义一个eor1 去异或数组找第x位为1的数,这样可以得到一个a，最后eor^eor1 得到 b

代码如下：

// arr中，有两种数，出现奇数次
	public static void printOddTimesNum2(int[] arr) {
		int eor = 0;
		for (int i = 0; i < arr.length; i++) {
			eor ^= arr[i];
		}
		// a 和 b是两种数
		// eor != 0
		// eor最右侧的1，提取出来
		// eor :     00110010110111000
		// rightOne :00000000000001000
		int rightOne = eor & (-eor); // 提取出最右的1
		
		
		int onlyOne = 0; // eor'
		for (int i = 0 ; i < arr.length;i++) {
			//  arr[1] =  111100011110000
			// rightOne=  000000000010000
			if ((arr[i] & rightOne) != 0) {
				onlyOne ^= arr[i];
			}
		}
		System.out.println(onlyOne + " " + (eor ^ onlyOne));
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

一个数组中有一种数出现K次，其他数都出现了M次， M > 1, K < M 找到，出现了K次的数， 要求，额外空间复杂度O(1)，时间复杂度O(N)

1)定义一个长度为32的数组t，将数组中所有数字每个位置的1都累加到t对应的位置里面
2)由于K<M（K和M不能是一样的整数倍），如果某个位置上出现的次数是M的整数倍，那么出现K次的数则不在那个位置上面。
代码如下：
包含对数器

public class Main {
    public static int test(int[] arr, int k, int m) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        for (int num : map.keySet()) {
            if (map.get(num) == k) {
                return num;
            }
        }
        return -1;
    }


    //保证arr中，只有一种数出现了K次，其他数都出现了M次
    public static int onlyKTimes(int[] arr, int k, int m) {
        int[] t = new int[32];
        //t[i] 代表i位置的1出现了几个
        for (int num : arr) {
            for (int i = 0; i <= 31; i++) {
               /* if (((num >> i) & 1) != 0) {
                    t[i]++;
                }*/
                t[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            //说明包含了出现K次的数
            if (t[i] % m != 0) {
                ans |= (1 << i);
            }
        }

        return ans;
    }

    public static int[] randomArray(int maxKinds, int range, int k, int m) {
        int kTimeNum = randomNumber(range);
        int numKinds = (int) (Math.random() * maxKinds) + 2;
        //一种数出现k次剩下的数出现了m次
        int[] arr = new int[k + (numKinds - 1) * m];
        int index = 0;
        for (; index < k; index++) {
            arr[index] = kTimeNum;
        }
        numKinds--;
        HashSet<Integer> set = new HashSet<>();
        set.add(kTimeNum);
        while (numKinds != 0) {
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            } while (set.contains(curNum));
            set.add(curNum);
            numKinds--;
            for (int i = 0; i < m; i++) {
                arr[index++] = curNum;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int j = (int) (Math.random() * arr.length);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        return arr;
    }

    // [-range, +range]
    public static int randomNumber(int range) {
        return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1));
    }

    public static void main(String[] args) {
        int kinds = 4;
        int range = 200;
        int testTime = 10000;
        int max = 9;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int a = (int) (Math.random() * max) + 1; // a 1 ~ 9
            int b = (int) (Math.random() * max) + 1; // b 1 ~ 9
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            // k < m
            if (k == m) {
                m++;
            }
            int[] arr = randomArray(kinds, range, k, m);
            int ans1 = test(arr, k, m);
            int ans2 = onlyKTimes(arr, k, m);
            int ans3 = test(arr, k, m);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println(ans1);
                System.out.println(ans3);
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束");
    }


}
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110