数组异或最大值_二进制异或运算怎么算

例1，寻找数组中丢失的数。。。 
有一组数字，从1到n减少了一个数，顺序也被打乱了，放在一个n-1的数组里，请找出丢失的数字。 
在上一篇“数组公式相关算法”里介绍过一些解法，不过，那样解的话，可能会有溢出的危险。我们可以利用位运算中的“异或” 来巧妙解决这个问题。 
算法步骤：1，对1-n个数做异或运算，得到XOR = 1^2^3^4….^n。 
2, 用XOR与当前n-1数组的所有元素依次取异或： 
因为XOR中与当前数字相同的数，都在异或运算中抵消掉了，最终剩下的，就是我们要找的那个丢失的数。

所谓抵消：举个例子： 1，1，2 
1： 0001 
2: 0010 1^1=0000 1^1^2 ===== 0000 ^ 0010 = 0010=2，也就是说两个1抵消了。 
任何一个数字异或它自己都等于0，而0与任何数字求异或，都为原数字！

例2，找出数组中两个只出现一次的数字 
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)

================== 以下全部引自原文 ======================= 
分析：这是一道很新颖的关于位运算的面试题。

首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现1次的数字，因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。

我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。

现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解决。

基于上述思路，我们不难写出如下代码：

/// 
// Find two numbers which only appear once in an array 
// Input: data – an array contains two number appearing exactly once, 
// while others appearing exactly twice 
// length – the length of data 
// Output: num1 – the first number appearing once in data 
// num2 – the second number appearing once in data 
/// 
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2) 
{ 
if (length < 2) 
return;

  // get num1 ^ num2
  int resultExclusiveOR = 0;
  for (int i = 0; i < length; ++ i)
        resultExclusiveOR ^= data[i];

  // get index of the first bit, which is 1 in resultExclusiveOR
  unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);

  num1 = num2 = 0;
  for (int j = 0; j < length; ++ j)
  {
        // divide the numbers in data into two groups,
        // the indexOf1 bit of numbers in the first group is 1,
        // while in the second group is 0
        if(IsBit1(data[j], indexOf1))
              num1 ^= data[j];
        else
              num2 ^= data[j];
  }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20

}

/// 
// Find the index of first bit which is 1 in num (assuming not 0) 
/// 
unsigned int FindFirstBitIs1(int num) 
{ 
int indexBit = 0; 
while (((num & 1) == 0) && (indexBit < 32)) 
{ 
num = num >> 1; 
++ indexBit; 
}

  return indexBit;

• 1
• 2

}

/// 
// Is the indexBit bit of num 1? 
/// 
bool IsBit1(int num, unsigned int indexBit) 
{ 
num = num >> indexBit;

  return (num & 1);

• 1
• 2

} 
原文地址：http://zhedahht.blog.163.com/blog/static/2541117420071128950682/ 
例3，腾讯10.09测试笔试题：有Ｎ＋２个数，N个数出现了偶数次，２个数出现了奇数次（这两个数不相等），问用O（1）的空间复杂度，找出这两个数，不需要知道具体位置，只需要知道这两个值。 
（@Rojay：xor一次，得到2个奇数次的数之和x。第二步，以x（展开成二进制）中有1的某位（假设第i位为1）作为划分，第二次只xor第i位为1的那些数，得到y。然后x xor y以及y便是那两个数。 ）

是不是对 “异或” 是啥有点疑惑或者记不清了？，那好， 
异或，也就是XOR　　 
1、异或是一个数学运算符。他应用于逻辑运算。 其运算法则为a异或b＝a’b+ab’（a’为非a）。 
　　2、例如：真异或假的结果是真，假异或真的结果也是真，真异或真的结果是假，假异或假的结果是假。就是说两个值不相同，则异或结果为真。反之，为假。 
　　异或运算法则： 
　　1. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c; 
　　2. d = a ^ b ^ c 可以推出 a = d ^ b ^ c. 
　　3、在计算机应用中，普遍运用，异或的逻辑符号 ^ (Shift + 6).形象表示为： 
　　真^假=真 
　　假^真=真 
　　假^假=假 
　　真^真=假 
　　或者为： 
　　True ^ False = True 
　　False ^ True = True 
　　False ^ False = False 
　　True ^ True = False 
　　部分计算机语言用1表示真，用0表示假，所以两个字节按位异或如下 
　　00000000 
　　异或 
　　00000000 
　　= 
　　00000000 
　　============我是分界线============ 
　　11111111 
　　异或 
　　00000000 
　　= 
　　11111111 
　　=============我还是分界线============= 
　　00000000 
　　异或 
　　11111111 
　　= 
　　11111111 
　　===========又是我。。。================ 
　　11111111 
　　异或 
　　11111111 
　　= 
　　00000000 
　　=============分界线===================== 
　　00001111 
　　异或 
　　11111111 
　　= 
　　11110000 
　　======================================== 
　　所以 按位异或 也常用于字节取反操作。 
　　————————————————————— 
　　异或还可以用来交换两个整形变量的值,而不需要第三个量的传递. 
　　例如： 
　　a=9; 
　　b=10; 
　　a=a^b; 
　　b=b^a; 
　　a=a^b; 
　　结果是a为10,b为9. 
　　4、异或和同或互为非运算。 

今天的文章数组异或最大值_二进制异或运算怎么算分享到此就结束了，感谢您的阅读。