本文共 5544 字，大约阅读时间需要 18 分钟。
异或是一个数学运算符，应用于逻辑运算，计算机符号为“eor”。
在二进制中，规则为：
1^0 = 1 1^1 = 0 0^0 = 0 也就是相同为0，不同为1，也可以理解为不带进位的二进制加法。举例：
5 ^ 3 = 6
5二进制：0 1 0 1
3二进制：0 0 1 1 异或： 0 1 1 0 = 61、归零率：a ^ a = 0（自己异或自己结果为0）
2、恒等率：a ^ 0 = a（与0异或结果不变） 3、交换律：a ^ b = b ^ a 4、结合律：a ^ b ^ c = a ^ (b ^ c )1、在不使用额外变量的前提下，完成两个数的交换。
public class Eor_01 { public static void main(String[] args) { int a = 1; int b = 2; //使用临时变量交换两个数 tempSwap(a, b); //使用异或方式 eorSwap(a, b); } private static void eorSwap(int a, int b) { System.out.println("eor交换前，a: " + a + "，b：" + b); a = a ^ b; // b = a ^ b 等于 b = a ^ b ^ b ，根据交换律得出 b = a ^ (b ^ b)，再根据归零率得出 b = a ^ 0，再根据恒等率得出 b = a，因此这一步完成了b被赋值成a b = a ^ b; //a = a ^ b 等于 a = a ^ b ^ a ， 同理a被赋值成了b，最终完成了两个数的交换。 a = a ^ b; System.out.println("eor交换后，a: " + a + "，b：" + b); } private static void tempSwap(int a, int b) { System.out.println("temp交换前，a: " + a + "，b：" + b); int c = a; a = b; b = c; System.out.println("temp交换后，a: " + a + "，b：" + b); }} 2、在一堆非空的整数数组中，只有一种数字出现了奇数次，其他数都出现了偶数次，找出这个奇数次的数字。
public class Eor_02 { public static void main(String[] args) { //只有4出现了奇数次，其他都出现了偶数次 int[] nums = { 1, 1, -2, 6, 4, 1, 1, 6, -2, 4, 4}; //一般的方式，利用hash统计每个数出现的次数，然后找出奇数的数字。 System.out.println(findOddNumberByHash(nums)); //eor方式 System.out.println(findOddNumberByEor(nums)); } private static int findOddNumberByEor(int[] nums) { /** * 还是根据结合律、归零率、恒等率可以理解为： 1 ^ 1 ^ 1 ^ 1 ^ -2 ^ -2 ^ 6 ^ 6 ^ 4 ^ 4 ^ 4 拆分为： 1 ^ 1 ^ 1 ^ 1 = 0 -2 ^ -2 = 0 6 ^ 6 = 0 4 ^ 4 = 0 0 ^ 0 ^ 0 ^ 0 = 0 剩下最后一个4 4 ^ 0 = 4 */ int oddNumber = 0; for (int i = 0; i < nums.length; i++) { oddNumber ^= nums[i]; } return oddNumber; } private static int findOddNumberByHash(int[] nums) { Map map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int k = nums[i]; map.put(k, map.getOrDefault(k, 0) + 1); } for (Map.Entry entry : map.entrySet()) { if (entry.getValue() % 2 != 0) { return entry.getKey(); } } return 0; }} 3、在一个长度为11数组中，放入1-10个数字，每个数字均出现了一次，再额外随机放入一个1-10的重复数字，找出这个重复的数字。
例如：[1,2,3,4,5,6,7,8,9,10,1]，重复数字为1，[1,2,3,4,5,6,7,8,9,10,4]，重复数字为4。
思路与上一题类似，变相的找出奇数次的数字。
public class Eor_03 { static Random random = new Random(); public static void main(String[] args) { int[] nums = new int[11]; for (int i = 1; i < nums.length; i++) { nums[i - 1] = i; } int oneTimes = random.nextInt(nums.length - 1) + 1; System.out.println("重复出现的数：" + oneTimes); nums[nums.length - 1] = oneTimes; System.out.println("打乱前：" + Arrays.toString(nums)); //打乱数组顺序，只是为了数组中数字随机的演示效果，与算法本身无关。 shuffle(nums); System.out.println("打乱后：" + Arrays.toString(nums)); findOneTimesNumber(nums); findOneTimesNumberByEor(nums); } private static void findOneTimesNumberByEor(int[] nums) { int k = 0; //先让数组中的每个数进行异或运算 for (int i = 0; i < nums.length; i++) { k ^= nums[i]; } //再把结果与 1-10 分别异或一次，最终得到的数就是重复出现的 for (int i = 1; i < nums.length; i++) { k ^= i; } System.out.println("eor方式找出重复出现的数：" + k); } private static void findOneTimesNumber(int[] nums) { int s1 = 0; int s2 = 0; for (int i = 1; i < nums.length; i++) { s1 += i; } for (int i = 0; i < nums.length; i++) { s2 += nums[i]; } System.out.println("累加方式找出重复出现的数：" + (s2 - s1)); } private static void shuffle(int[] nums) { for (int i = 0; i < nums.length; i++) { int r = random.nextInt(nums.length - 1) + 1; int temp = nums[i]; nums[i] = nums[r]; nums[r] = temp; } }} 4、一个数组中，有两种数出现了奇数次，其他都出现了偶数次，找出这两种数。
public class Eor_04 { public static void main(String[] args) { int[] nums = { 1, 8, 8, 4, 2, 3, 1, 2, 2, 3}; findTwoOddNumberByEor(nums); } private static void findTwoOddNumberByEor(int[] nums) { int k = 0; //先让所有数进行异或运算，得到的结果肯定是两个奇数异或的值，用变量k存储着。 for (int i = 0; i < nums.length; i++) { k ^= nums[i]; } /** * 从k中随便找一个二进制位上，下标为1的，k & (~k + 1)可以找到二进制上最右侧的1（只要找到下标有1的位置就可以了，哪一个无所谓，这里用个算法取巧，得到最右侧的1）。 * 假设这个1在第2位，那么数组中就分为两类数，一类是第2位为1的，一类是第2位为0的。 * 就等于把两个奇数拆分出来了。 * * 验证，假设数组为：{1, 8, 8, 4, 2, 3, 1, 2, 2, 3} * * 分别计算二进制 * 1:0001 * 8:1000 * 4:0100 * 2:0010 * 3:0011 * * 两个奇数异或结果 * 2 ^ 4 = 0110 * * 0110最右侧的1在第2位，即得到：0010 * * 第2位为1的数有 2,3 * 第2位为0的数有 1,8,4 * * 再让数组中所有的1,8,4异或，就得到了4 * 再用4异或 2 ^ 4 就得到了 2 * */ int a = k & (~k + 1); int m = 0; for (int i = 0; i < nums.length; i++) { int num = nums[i]; //如果 (num & a) != 0 则表示 第2位一定不为0 if ((num & a) != 0) { m ^= num; } } int n = k ^ m; System.out.println("两个奇数分别为：" + m + "," + n); }} 转载地址：http://zqlrb.baihongyu.com/