经典面试之——异或操作

自用笔记算法

经典面试之——异或操作

例题一

题目要求

一个整型数组里除了一个数字(奇数次数字)出现1次（奇数次）之外 其他数字都出现了两次 请写出程序找出这个数字
要求时间复杂度n 空间复杂度1

思路

依次异或 出现两次的数字异或等于0 所以那个出现1次或奇次的数字最后讲浮现出来

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
include<iostream>
using namespace std;
int main()
{
	int T;
	cin>>T;
	long long temp,ans;
	while(T--)
	{
		int N;
		cin>>N;
		N--;
		cin>>temp;
		ans=temp;
		while(N--)
		{
			cin>>temp;
			ans^=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

例题二

题目要求

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

思路

如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办法就
是分别求出这两个只出现一次的数字了。
我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部
抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到
第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个
子数组的每个数字的第N位都为0。
现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。因此到此为止，所有的问题我们都已经解
决。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000050];
void FindNumsAppearOnce(int* data, int length)
{
    int OR = 0 ;
    for (int i = 0 ; i < length ; i++)//依次异或数组中的每一个数
        OR = OR ^ data[i] ;
    int index = 1 ;
    while ((OR & 1) != 1 && (index < 32))//从右向左找到异或结果中第一个为1的位的位置
    {
        OR = OR>>1;
        index++;
    }
    int num1 = 0 ;
    int num2 = 0 ;
    for (int j = 0 ; j < length ;j++)
    {
        int temp = data[j];
        temp = temp >> (index - 1) ;//向右移位到index的位置
        if ((temp & 1) == 1) //判断该位是否为1
            num1 = num1 ^ data[j];
        else
            num2 = num2 ^ data[j] ;
    }
    cout<<min(num1,num2)<<" "<<max(num1,num2)<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		FindNumsAppearOnce(a,n);
	}
}

例题三

题目要求

一个数组中有三个数字a、b、c只出现一次，其他数字都出现了两次。请找出三个只出现一次的数字

思路

考虑给定数组中有三个单独出现一次的数字，这个会比有两个的稍微复杂。分步分析，设定这三个数为a,b,c:
(1)将数组中的数字全部异或，得到的结果x=a^b^c，但是x不是a，b，c中的其中一个，假设x=a，那么b^c=0说明b=c，与题目给定的条件矛盾。
(2)设定f(n)可以像2中的那样，从低位开始，找到第一个bit为1的位置，f(x^a),f(x^b),f(x^c)得到的值肯定都不为0，因为x^a,x^b,x^c本身就不为0。
f(x^a)^f(x^b)^f(x^c)结果不为0。因为f(x^a)^f(x^b)的结果中可能为0，也可能有两个bit为1。如果假设f(x^c)的结果bit为1的位置与f(x^a)^f(x^b)的
其中一个重合，则f(x^a)^f(x^b)^f(x^c)结果中只有1个bit为1，如果不重合的话那么有3个bit位为1。
(3)这便可以推断出f(x^a)^f(x^b)^f(x^c)中至少有一个bit位为1。假设从低位到高位的第mbit位为1.那么可以得出结论x^a,x^b,x^c中有一个或者三个的
第m位为1（不可能有两个，因为有两个的话，异或的结果就为0了）。
(4)证明，x^a,x^b,x^c中只有一个第m-bit位为1.假设他们的第m位都为1，那么x的第m位为0，但是x=a^b^c其第m位肯定为1，所以假设不成立。那么相反，
假设x的第m位为1，a,b,c的第m位都为0，也不成立，因为x=a^b^c。所以综上所述x^a,x^b,x^c中只有一个第m位为1。那么这个问题就好办了。根据这个
第m位找到第一个只出现一次的数字。然后剩下两个就是问题2所描述的问题。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int get_first_bit(int num)   //效其果是最低位的1不变 其余清0
{  
	return num&~(num-1);  
}  
void get_two_unique_num(int *a,int n,int *num1,int *num2)  
{  
	int result_code=0;  
	for(int i=0;i<n;i++)  
		result_code^=a[i];  
	int diff=get_first_bit(result_code);    //最低位为1 其余位为0
	*num1=0;  
	*num2=0;  
	for(int i=0;i<n;i++)  
	{  
		if(a[i]&diff)         //不同与例题二的操作 此方法不需要找出最低位1的位置
		{  
			(*num1)^=a[i];  
		}  
		else  
		{  
			(*num2)^=a[i];  
		}  
	}  
}  
void get_three_unique_num(int *a,int n,int *num1,int *num2,int *num3)  
{  
	int result_code=0;  
	for(int i=0;i<n;i++)  
		result_code^=a[i];            //最后结果为x=a^b^c
	int flag=0;  
	for(int i=0;i<n;i++)  
		flag^=get_first_bit(result_code^a[i]);   //x^a x^b x^c 分别进行最低位为1 其余清0的操作
	flag=get_first_bit(flag);            //再把这三个数^再进行清0操作 得到的就是只有最低位为1的数字
	*num1=0;  
	for(int i=0;i<n;i++)  
	{  
		if(get_first_bit(result_code^a[i])==flag)  //以最低位的1为基准 只要该位为1的数字全部^ 
		{                                         //即可求出num1
			(*num1)^=a[i];  
		}  
	}  
	for(int i=0;i<n;i++)               //把num1与数组最后一位交换 前面的n-1个数字进行与问题二相同的操作
	{  
		if(a[i]==(*num1))  
		{  
			int temp=a[i];  
			a[i]=a[n-1];  
			a[n-1]=temp;  
			break;  
		}  
	}  
	get_two_unique_num(a,n-1,num2,num3);  
}  
void main()  
{  
	int a[]={2,2,4,4,6,6,3,5,7};  
	int num1,num2,num3;  
	get_three_unique_num(a,sizeof(a)/sizeof(int),&num1,&num2,&num3);  
	printf("%d\t%d\t%d\n",num1,num2,num3);  
}

例题四

题目要求

给出1-1000个连续自然数，然后从中随机去掉两个，再打乱顺序，要求只遍历一次，求出被去掉的两个数。

思路

首先，这两个数组(打乱前和打乱后)各自异或，也就是1^2^…^1000，得到两个异或值。再对这两个异或值进行一次异或，这样就得到了x^y的指(重复部分互相
抵消了)。
因为x和y是两个不同的整数，所以这两个数的异或结果，转化为二进制的话，一定在某位是1，假设在第3位。也就是说如果把原始数组按第3位是否为0进行划
分，就可以分成两个数组，每个数组各包含一个被抽取的数。如果打乱后的数组也按这个规则划分为两个数组，这样就得到了4个数组，其中两组是第3位为0,
另外两组是第3位为1。把第3位为0的两个数组所有元素进行异或就能得到被抽取的一个数，同理也就能获得另外一个被抽取的数，于是问题解决。

例题五

题目要求

数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法，找到x。

思路

乍一看这个题目，不少同学立马给出了答案：异或。但举个例子，就会发现，异或是行不通的，一般的方法是利用异或的的如下特性：
A xor A = 0
A xor 0 = A
但是这个题目中，数字都是奇数个的，直接采用之前类似题目的异或方法，已经不合适了。

除此之外，我们还可能想到如下的方法：
（1）采用hashmap，时间复杂度O(n)，空间复杂度O(n)
（2）对数组A进行排序，然后在遍历一次，时间复杂度O(nlogn)，空间复杂度O(1) 这个方法还可以。

是否还有一些效果更好的方法呢？这一类的题目，即使简单的异或不能解决，也可以从二进制位、位操作方面去考虑，总之这样的大方向是不会错的。
题目中，如果数组中的元素都是三个三个出现的，那么从二进制表示的角度，每个位上的1加起来，应该可以整除3。如果有一个数x只出现一次，会是什么
情况呢？
如果某个特定位上的1加起来，可以被3整除，说明对应x的那位是0，因为如果是1，不可能被3整除
如果某个特定位上的1加起来，不可以被3整除，说明对应x的那位是1
根据上面的描述，我们可以开辟一个大小为32的数组，第0个元素表示，A中所有元素的二进制表示的最低位的和，依次类推。最后，再转换为十进制数即可。
这里要说明的是，用一个大小为32的整数数组表示，同样空间是O(1)的。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;
void set(int& a,int i) { a |= (1<< (i & 0x1F));}  //把a第i位置为1
void clr(int& a,int i) { a &= ~(1<<(i & 0x1f));}  //把a的第i位清0
void find(int a[],int n)
{
    int m[32];
    for(int i=0;i<32;i++)
        m[i]=0;
    for(int i=0;i<32;i++)
    {
        for(int j=0;j<n;j++)
        {
            int bit=a[j]&1;
            m[i]+=bit;
            a[j] >>=1;
        }
    }
    int result=0;
    for(int i=0;i<32;i++)
    {
        if(m[i]%3!=0)
            set(result,i);
    }
    cout<<"结果为"<<result<<endl;
}
int main()
{
    int a[]={1,2,2,2,3,3,3};
    int n=sizeof(a)/sizeof(a[0]);
    find(a,n);
}

经典位运算总结

（1） n&（n-1）

1
把最低为的1变成0 原本是0不变 用于计算二进制数中1的个数

（2） n&~（n-1）

1
在n-1前加了取反符号 作用是保留n中最低位的1 其余位均清零

（3）把a第i位置为1

1
void set(int& a,int i) { a |= (1<< (i & 0x1F));}

（4）把a的第i位清0

1
void clr(int& a,int i) { a &= ~(1<<(i & 0x1f));}

（5）获取第i位(2^i次方形式)

1
int test(int& a,int i) { return a&= (1<<(i & 0x1F));}

（6）a&1

1
2
判断a的最后一位数字是0还是1 用于判断奇偶性 也可用于二进制数每一位的相加运算 寻找最低位1的位置
判断二进制中x到y位中1的个数等等。

（7）&1 |1

1
只有1&1结果才为1 只有0|0结果才为0

（8）交换两个数字

1
2
3
4
5
6
void swap(int x , int y) 
{ 
    x =x^y; 
    y =x^y; 
    x =x^y; 
}

（9）返回整数的平均值

1
2
3
4
int average(int x, int y) 
{    
    return (x&y)+((x^y)>>1); 
}

（10）对于一个数x，判断他是不是2的幂

1
2
3
4
boolean power2(int x) 
{ 
    return (x&(x-1))==0； 
}

（11）计算绝对值

1
2
3
4
5
6
int abs( int x ) 
{ 
int y ; 
y = x >> 31 ; 
return (x^y)-y ;        //or: (x+y)^y 
}

（12）取模运算转化成位运算 (在不产生溢出的情况下)

1
a % (2^n) 等价于 a & (2^n - 1)

（13）乘法运算转化成位运算 (在不产生溢出的情况下)

1
a * (2^n) 等价于 a < < n

（14）除法运算转化成位运算 (在不产生溢出的情况下)

1
2
a / (2^n) 等价于 a>> n 
例: 12/8 == 12>>3

（15）x 的 相反数 表示为 (~x+1)
（16）求从x位（高）到y位（低）间共有多少个1

1
2
3
4
5
6
7
8
9
int FindChessNum(int x, int y, int k) 
{ 
	int re = 0; 
	for (int i = y; i <= x; i++) 
	{ 
		re += ((k >> (i - 1)) & 1); 
	} 
	return re; 
}

本文标题:经典面试之——异或操作

文章作者:Hippopmonkey

发布时间:2017-02-06, 12:24:00

最后更新:2017-02-06, 14:49:31

原始链接:http://xuboming8.github.io/2017/02/06/经典面试之——异或操作/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 经典面试之——异或操作
    1. 1.1. 例题一
      1. 1.1.1. 题目要求
      2. 1.1.2. 思路
      3. 1.1.3. 参考代码
    2. 1.2. 例题二
      1. 1.2.1. 题目要求
      2. 1.2.2. 思路
      3. 1.2.3. 参考代码
    3. 1.3. 例题三
      1. 1.3.1. 题目要求
      2. 1.3.2. 思路
      3. 1.3.3. 参考代码
    4. 1.4. 例题四
      1. 1.4.1. 题目要求
      2. 1.4.2. 思路
    5. 1.5. 例题五
      1. 1.5.1. 题目要求
      2. 1.5.2. 思路
      3. 1.5.3. 参考代码
    6. 1.6. 经典位运算总结
|