《编程之美》读书笔记：快速找出故障机器

最近在学习《 编程之美 》这本书，书中提到了很多很经典的算法问题和实现，学起来真是耗费脑细胞啊。书中的算法实现使用C编写的，这里作者自己写了一部分java的实现，如果有错误，还请各位读者批评指正。截图版权属于原作者。

github：

【 https://github.com/cstriker1407/think_in_java 】

1.5快速找出故障机器

解法三

public class NumSearchTest
{
	/*
	 * 通过异或的方式来快速找到落单的那个数字。
	 * 
数学运算方式异或有如下的几个运算特性，
1. a ⊕ a = 0 和  a⊕ 0 = a
2. a ⊕ b = b ⊕ a
3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c
5. a ⊕ b ⊕ a = b
通过这些特性，可以发现异或遵循交换律，当数组中的有一个落单的数时，其他的所有数均可两两异或为0，剩下的落单数与0异或得到原值
	 */
	public static void test()
	{
		List<Integer> numList = new LinkedList<Integer>();
		for (int i = 0; i < 1000; i++)
		{
			numList.add(i);
			numList.add(i);
		}
		int key = 666;
		numList.remove(new Integer(key));
	
		int searchResult = 0;
		for (Integer item : numList)
		{
			searchResult = searchResult ^ item;
		}
		System.out.println("result:" + searchResult);
	}
}

 备注：

1）作者只实现了解法3，其他解法作者没有使用java实现。

2）通过代码可以发现，熟练使用运算符（加减乘除 同或异或 左右移）可以在特定需求下写出非常漂亮的代码。看来数学还是得好好学习啊~~