转载高效实用的异或操作

异或(XOR)是一种位运算符，相同为0，相异为1

如0^1=1,0^0=0,1^1=0

异或满足交换律、结合律

a^b=b^a

a^(b^c)=a^b^c=(a^b)^c

a^b^c^d=a^d^c^b

异或是一种位运算，能够高效地巧妙地完成一些功能

1、实现两个数的交换，swap函数

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];
	}

2、在一组数中，只有一个数只出现一次，其他数都出现两次，请找出这个只出现一次的数

见到这个问题，第一反应就是依次拿出每一个数字和整个数组比较，若某一数字没有与之相等的元素，则输出这个数字。这是最容易想到也是最笨的方法，算法复杂度为O(n²)

有没有一种只遍历一次数组就可以找出这个数的方法呢。很多时候，我们都会用以空间换时间的方法来降低算法的时间复杂度。于是，对于这个问题，我们又想到遍历一次数组把每个数出现的次数存起来，然后再找出只出现一次的数字。要记录每个数的出现次数，可以用map来实现，键来标识数字，值来标识键在数组中出现的次数。这样遍历一次数组就可以形成一个键值对，然后再遍历这个map，找出值为1的那个键即可。这种方法实现起来也很简单。

在这个数组中既然只有一个数出现一次，其他数都出现两次。根据异或的性质，我们把这组数互相异或一下，相同的数结果为0，最后只剩下出现次数为1的那个数了。

/**
	 * 数组 异或
	 * @param arr
	 * @return 数组中所有数值异或的结果
	 */
	public static int xorArray(int[] arr) {
		int length = 0, res = 0;
		length = arr.length;
		for (int i = 0; i < length; i++) {
			res ^= arr[i];
		}
		return res;
	}

3、对上一个问题再提升一个难度，如果在一组数中只有两个数只出现一次，其他数字都出现两次，请找出这两个数字

我们套用上边的思路如果对数组中全部数字异或，最后只得到一个数，这个数是要求的这两个数的异或结果。但是从这个异或结果不能把要求的两个数分离出来。

仔细分析这个异或值，假如这两个数的二进制值分别为001010和001110，异或结果为000100，也就是两个数中不同的位为1。因为这两个数不同，异或结果肯定至少有一位为1。我们任取一位为1的位，依据这一位是否为1把整个数组分成两部分。这样这两个数就分在了不同的组中。然后再对每一个部分按照方法2异或得出结果。

到这里有人可以会有疑问，把数组分割成两部分，如果相同的两个数分在不同的组中结果不就不对了吗。我们分组的依据是某一位是否为1，如果两个数相同，那么这一位也肯定相同，这样两个相同的数肯定会分到同一组中。实现代码如下：

/**
 * 数组中只有两个数不成双，其数字都是成双的，输出这两个数
 * @author 王竹
 */
package com.wangzhu.demo;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(new BufferedInputStream(System.in));
		int[] arr = null;
		int length = -1, res = -1, res1 = -1, res2 = -1, temp = -1;
		while (cin.hasNext()) {
			length = cin.nextInt();
			arr = new int[length];
			for (int i = 0; i < length; i++) {
				arr[i] = cin.nextInt();
			}
			res = xorArray(arr);
			temp = (res ^ ((res - 1) & res));//获得res二进制中最右的1
			res1 = 0;
			res2 = 0;
			for (int i = 0; i < length; i++) {
				if ((temp & arr[i]) == 0) {
					res1 ^= arr[i];
				} else {
					res2 ^= arr[i];
				}
			}
			for (int i : arr) {
				System.out.print(i + " ");
			}
			System.out.println("\n" + res1 + " " + res2);
		}

	}

	/**
	 * 数组 异或
	 * @param arr
	 * @return 数组中所有数值异或的结果
	 */
	public static int xorArray(int[] arr) {
		int length = 0, res = 0;
		length = arr.length;
		for (int i = 0; i < length; i++) {
			res ^= arr[i];
		}
		return res;
	}
}

异或是一种位操作，实现起来非常高效

转载 高效实用的异或操作

转载高效实用的异或操作