JAVA利用异或找不同数字算法,java炙风的博客-

游戏介绍

大家小的时候应该都玩过连连看，选择两个相同元素即可消掉。那么我们换个玩法：
假如目前有49对情侣（相同的元素)，以及1位单身贵族（不同的元素），你能迅速找到那位孤独的元素做你女朋友吗?

想法

“一切孤独皆是罪过”

你或许开始将相同的元素划掉，然后一个一个找；亦或许是你将所有元素抄下来计数。但是你有没有想过，这里只有99个数。如果有999个数呢？9999个数呢？
我相信你都明白了为什么尼采说一切孤独皆是罪过了。究竟要怎么才能找到那位梦中情人呢？

工具

人和动物的区别，是会创造和使用工具。有没有那么一面镜子，能够让情侣们消失，单身狗显现呢？
“异或！！！”
数学里的符号为：⊕；计算机中为：xor，它满足一下规则：

1 xor 1 = 0 0 xor 0 = 0 1 xor 0 = 1 0 xor 1 = 1 

此法则满足：交换律与结合律。

使用

有了工具，我们也要会使用，我们可以看到，异或操作会将相同的元素湮灭掉（0），不同的元素只显示未被湮灭的（1）。
此时，我们观察刚开始游戏中的元素：它们都是有自己对应的十进制数字。我们将这些数字全部转为二进制然后按位做异或运算，相同的数字或者说成双结对的全部灰飞烟灭，得出的结果即为“孤独患者”。

Integer[] nums = {1,2,2,41,36,41,42,39,39,45,3,1,3,35,33,33,32,40,45,44,4,4,6,17,35,34,11,46,42,46,5,6,7,12,16,15,32,44,47,34,7,8,8,5,15,10,36,43,48,43,13,13,11,12,14,14,22,31,21,47,26,16,27,19,50,22,37,40,17,18,26,29,28,23,23,24,37,21,20,10,27,48,50,18,24,38,9,31,20,9,28,49,49,25,25,29,38,30,30}; int num = 0; for (int i = 0;i<nums.length;i++) {    num = nums[i]^num; } System.out.println(num); 

答案：19

扩展

假如目前有n对元素，以及2个单独出现的元素，你能迅速找到那两位孤独的元素让其结婚吗?

方案

我们按照按起初的方法跑一遍程序：

Integer[] nums = {1,2,2,41,36,41,42,39,39,45,3,1,3,35,33,33,32,40,45,44,4,4,6,17,35,34,11,46,42,46,5,6,7,12,16,15,32,44,47,34,7,8,8,5,15,10,36,43,48,43,13,13,11,12,14,14,22,31,21,47,26,16,27,19,50,22,37,40,17,18,26,29,28,23,23,24,37,21,20,10,27,48,50,18,24,38,9,31,20,51,28,49,49,25,25,29,38,30,30,51}; int num =0; for (int i = 0;i<nums.length;i++) {  num = nums[i]^num; } System.out.println(num); 

得出的结果为：26
注意，此时的26并非是说26是单独的元素。而是两个单独元素异或运算后的结果。
我们将26改为二进制，即：11010，我们知道，异或操作是相同为0，相异为1.所以我们可以反推，那两个元素一定是：异异同异同。举个例子：
若A为11010（26）则B为00000（0）；
若A为10010（18）则B为01000（8）
我们可以任取一个两元素为异的位，比如我们取倒数第4位：异 异 同异同 ，按位的不同分组，分组后就相当于两个第一种情况，然后分别求单身狗即可。
代码如下：

Integer[] nums = {1,2,2,41,36,41,42,39,39,45,3,1,3,35,33,33,32,40,45,44,4,4,6,17,35,34,11,46,42,46,5,6,7,12,16,15,32,44,47,34,7,8,8,5,15,10,36,43,48,43,13,13,11,12,14,14,22,31,21,47,26,16,27,19,50,22,37,40,17,18,26,29,28,23,23,24,37,21,20,10,27,48,50,18,24,38,9,31,20,51,28,49,49,25,25,29,38,30,30,51}; int num =0; for (int i = 0;i<nums.length;i++) {       num = nums[i]^num; } int flag =1 ; while((num&flag)==0) {       flag<<=1; } int num1 = 0; int num2 = 0; for(int i = 0;i<nums.length;i++) { if((nums[i]&flag)==0) {                num1=nums[i]^num1; }else {        num2= nums[i]^num2; } }      System.out.println("num1:"+num1+",num2:"+num2); 

结果为：num1:9,num2:19

祝有情人终成眷属