异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处：http://blog.csdn.net/ns_code/article/details/27568975

    这篇文章没有代码，介绍的是纯理论的思路。

    异或是一种基于二进制的位运算，用符号XOR或者 ^ 表示，其运算法则是对运算符两侧数的每一个二进制位，同值取0，异值取1。它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。

    异或的性质：

    1、交换律：a^b = b^a；

    2、结合律：(a^b)^c = a^(b^c)；

    3、对于任意的a：a^a=0，a^0=a，a^(-1)=~a。

    了解了上面这些，来看看这个，很重要，后面的程序都要用到这个结论：

    对于任意的a，有a^b^c^d^a^k = b^c^d^k^(a^a) = b^c^d^k^0 = b^c^d^k，也就是说，如果有多个数异或，其中有重复的数，则无论这些重复的数是否相邻，都可以根据异或的性质将其这些重复的数消去，具体来说，如果重复出现了偶数次，则异或后会全部消去，如果重复出现了奇数次，则异或后会保留一个。

    下面来看两道题目：

     1、1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？

    当然，这道题，可以用最直观的方法来做，将所有的数加起来，减去1+2+3+...+1000的和，得到的即是重复的那个数，该方法很容易理解，而且效率很高，也不需要辅助空间，唯一的不足时，如果范围不是1000，而是更大的数字，可能会发生溢出。

    我们考虑用异或操作来解决该问题。现在问题是要求重复的那个数字，我们姑且假设该数字式n吧，如果我们能想办法把1-1000中除n以外的数字全部异或两次，而数字n只异或一次，就可以把1-1000中出n以外的所有数字消去，这样就只剩下n了。我们首先把所有的数字异或，记为T，可以得到如下：

T = 1^2^3^4...^n...^n...^1000 = 1^2^3...^1000（结果中不含n）

    而后我们再让T与1-1000之间的所有数字（仅包含一个n）异或，便可得到该重复数字n。如下所示：

T^(a^2^3^4...^n...^1000) = T^(T^n) = 0^n = n

    这道题到此为止。

    2、一个数组中只有一个数字出现了一次，其他的全部出现了两次，求出这个数字。

    明白了上面题目的推导过程，这个就很容易了，将数组中所有的元素全部异或，最后出现两次的元素会全部被消去，而最后会得到该只出现一次的数字。

    该题目同样可以该为如下情景，思路是一样的：数组中只有一个数字出现了奇数次，其他的都出现了偶数次。

题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。输入：

每个测试案例包括两行：

第一行包含一个整数n，表示数组大小。2<=n <= 10^6。

第二行包含n个整数，表示数组元素，元素均为int。

输出：对应每个测试案例，输出数组中只出现一次的两个数。输出的数字从小到大的顺序。样例输入：

8
2 4 3 6 3 2 5 5

样例输出：

4 6

    思路：上篇博文中已经了解到异或去重的原理，而且知道如果只有一个只出现一次的数字的求法，但这里是有两个只出现一次的数字，我们便要想办法把他分为两个子数组，每个子数组中包含一个只出现一次的数字，其他的数字都出现了两次。剑指offer上的思路很巧妙，依然从头到尾异或所有的数字，这样得到的结果实际上就是两个只出现了一次的数字异或的结果，我们在异或后的结果中找出其二进制中最右边为1的位，该位既然为1，说明异或的两个数字对应的该位肯定不同，必定一个为1，一个为0，因此我们可以考虑根据此位是否为1来划分这两个子数组，这样两个只出现一次的数字就分开了，但我们还要保证出现两次的数字都分到同一个子数组中，肯定不能两个重复的数字分在两个不同的子数组中，这样得到的结果是不对的，很明显，相同的数字相同的位上的值是相同的，要么都为1，要么都为0，因此我们同样可以通过判断该位是否为1来将这些出现两次的数字划分到同一个子数组中，该位如果为1，就分到一个子数组中，如果为0，就分到另一个子数组中。这样就能保证每个子数组中只有一个出现一次的数字，其他的数字都出现两次，分别全部异或即可得到这两个只出现一次的数字。时间复杂度为O(n)。

    另外，所有元素异或后，在找出最右边为1的时，我用的比剑指offer上更简洁的代码，主要用到了下面的结论：

对于一个数字X，X&(-X)之后得到的数字，是把X中最右边的1保留下来，其他位全部为0。注意，这里的-X是X的相反数，-X=~X+1，这里的~X意思是对X所有位取反，不要将二者弄混了。

    下面是AC的代码：

[cpp] view plaincopy

1. #include<stdio.h>
2. #include<stdbool.h>
4. /*
5. 返回num的最低位的1，其他各位都为0
6. */
7. int FindFirstBit1(int num)  
8. {  
9. //二者与后得到的数，将num最右边的1保留下来，其他位的全部置为了0
10. return num & (-num);  
11. }  
13. /*
14. 判断data中特定的位是否为1，
15. 这里的要判断的特定的位由res确定，
16. res中只有一位为1，其他位均为0，由FindFirstBit1函数返回，
17. 而data中要判断的位便是res中这唯一的1所在的位
18. */
19. bool IsBit1(int data,int res)  
20. {  
21. return ((data&res)==0) ? false:true;  
22. }  
24. void FindNumsAppearOnce(int *arr,int len,int *num1,int *num2)  
25. {  
26. if(arr==NULL || len<2)  
27. return;  
29. int i;  
30. int AllXOR = 0;  
31. //全部异或
32. for(i=0;i<len;i++)  
33.         AllXOR ^= arr[i];  
35. int res = FindFirstBit1(AllXOR);  
37.     *num1 = *num2 = 0;  
38. for(i=0;i<len;i++)  
39.     {  
40. if(IsBit1(arr[i],res))  
41.             *num1 ^= arr[i];  
42. else
43.             *num2 ^= arr[i];  
44.     }  
45. }  
47. int main()  
48. {  
49. static int arr[1000000];  
50. int n;  
51. while(scanf("%d",&n) != EOF)  
52.     {  
53. int i;  
54. for(i=0;i<n;i++)  
55.             scanf("%d",arr+i);  
57. int num1,num2;  
58.         FindNumsAppearOnce(arr,n,&num1,&num2);  
59. if(num1 < num2)  
60.             printf("%d %d\n",num1,num2);  
61. else
62.             printf("%d %d\n",num2,num1);  
63.     }  
64. return 0;  
65. }