与异或操作相关的简单算法题

异或运算的性质

1、0 ^ N == N， N ^ N==0 2、异或运算满足交换律和结合律

题目1：如何不使用额外变量交换两个数

int a  == 甲； int b = 乙；
a = a ^ b;
b = a ^ b;
a = a ^ b;

把上面代码分为三个步骤 第一步： a = a ^ b; 此步骤过后 a = 甲 ^乙；b = 乙； 第二步： b = a ^ b; 此步骤过后 a = a ^ b = 甲 ^ 乙；b = a ^ b = 甲 ^ 乙 ^ 乙 = 甲； 第三步： a = a ^ b; 此步骤过后b = 甲； a = a ^ b = 甲 ^ 乙 ^ 甲 = 乙； 完成交换 注意：两个交换的数不能指向相同内存！！！

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

方法：遍历数组所有元素，一直异或。因为两个相同的数异或为0，所以异或到最后的数就是出现奇数次的数。

public static void printOddNumber1(int[] arr) {
	int eor = 0;
	for (int i = 0; i < arr.length; i++){
		eor = eor ^ arr[i];
	}
	System.out.println(eor)
}

题目3：怎么把一个int整型数，二进制位最右侧的1提取出来

例如：输入1001……01000 输出0000……01000 方法：加入输入的为N，这输出为 N & (~N + 1) 步骤： 输入：1001……01000 取反：0110……10111 再加一：0110……11000 相与：0000……01000

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

思路： 1、按照题目2的方法，全部的数一起异或，得到eor = a ^ b 2、按照题目3的方法，提取eor最右边1(其实任意一个一都行，因为值为1的地方表示两个数在该位不同)，根据这个位是否为1，将数组分为A、B两部分。 3、对A部分的数进行一起进行异或运算，得到数1，将数1与eor异或得到数2

public static void printOddNumber(int [] arr) {
	int eor = 0;
	for (int i = 0; i < arr.length; i++) {
		eor = eor ^ arr[i];
	}
	int rightOne = eor & (~eor + 1);
	int numA = 0;
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] & eor == 0) {
			numA = numA ^ arr[i];
		}
	}
	numB = eor ^ numA;
}

题目5：获得一个数二进制位，为1的个数

public static int bitCount(int N) {
	int count = 0;
	while (N != 0){
		int rightOne = N & ((~N) + 1);
		count++;
		N = N ^ rightOne;
	}
	return count;
}