本文主要是介绍[面试] 关于异或的四道典型题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1，假设函数f(n)是自然数1，2，3,...,n的所有数的异或，即f(n)=1^2^3^...^n, 那么，任意的n（n为自然数），我们能够很快的计算出f(n)的值
- if n == 4*m, then f(n) = n
- else if n == 4*m + 1, then f(n) = 1
- else if n == 4*m + 2, then f(n) = n+1
- else n = 0
另外，异或的一些基本的性质：
1. 交换律
2. 结合律
3. x^x = 0, 0^x=x, a^b^a=b
2, 利用异或的这些性质，我们可以在不需要任何额外空间的情况下交换两个变量的值：
方法如下：利用异或交换整数a，b的值。
- a ^= b;
- b ^= a;
- a ^= b;
3, 一道有趣的题目：
1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现
一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空
间，能否设计一个算法实现？
这题一个很简单的解法是将1001个数相加再减去1-1000的和，但是如果数据更大可能导致计算的和太大而溢出。
但是如果用异或运算则不会有这个担心。
方法： 将1001个数进行异或，在与1-1000的异或进行异或4,有N个整数，除了其中的两个数只出现一次以外，其余的所有的数都正好出现两次，如何用最快的方法求出只出现一次的两个数，要求空间复杂度是O(1).
三 解决方案首先 回忆 异或操作，任意数字与自身相异或，结果都为0.还有一个重要的性质，即任何元素与0相异或，结果都为元素自身。解决方案：1 从数组的起始位置开始，对元素执行异或操作，则最后的结果，即为此只出现了一次的元素。2 题目中，数组中存在两个不同的元素，若是能仿造上述的解决方案，将两个元素分别放置在两个数组中，然后分别对每个数组进行异或操作，则所求异或结果即为所求。3 首先对原数组进行全部元素的异或，得到一个必然不为0的结果，然后判断该结果的2进制数字中，为1的最低的一位。然后根据此位是否为1 ，可以把原数组分为两组。则两个不同的元素，必然分别在这两个数组中。4 然后对两个数组，进行异或操作，即可得到所求。四 代码示例
#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;
const int N = 10;int getSingle(int *a) { //获取全部元素的异或结果 if(!a) { // return -1;}int sum = a[0];for(int i = 1; i < N; i++) {sum ^= a[i];}return sum;
}
void getTwo(int *a, int &one, int &two, int sum) {unsigned int flag = 1;while(1) {if(flag&sum)break;flag = flag << 1;}one = 0;two = 0;for(int i = 0; i < N; i++) {if(a[i]&flag) {one ^= a[i];}else {two ^= a[i];}}cout << sum << ' ' << one << ' ' << two << endl;
}
int main() {int a[N] = {3, 5, 8, 8, 5, 3, 1, 4, 4, 10}; int single = getSingle(a);int one = 0;int two = 0;getTwo(a, one, two, single);system("pause");return 0;
}这篇关于[面试] 关于异或的四道典型题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
