算法提升（二） 异或法

作者：@小萌新
专栏：@算法提升
作者简介：大二学生 希望每天能够输出优质内容
内容简介：本文会较为详细的介绍异或以及异或法的使用

要加油 照顾好自己

异或是什么？

1. 概念

异或就是无进位相加！
异或就是无进位相加！
异或就是无进位相加！

现在 忘掉之前学到的所有东西 记住这句话

比如说 这里给你两个二进制数

0 0 0 0 1 0 1 0
0 0 0 1 0 1 1 1

我们将它们无进位相加之后 是不是就能得到

0 0 0 1 1 1 0 1

这个是不是就是它们异或的结果啊

2. 性质

异或满足交换律和结合律

说人话 是什么意思呢？

就是说 相同的一堆数组 不管它们怎么异或 最后的结果一定还是一样的

还记得我在开头说的话嘛？

异或就是无进位相加

假设我们这里给出五个数

a b c d e

那么请问 它们在第一位上的二进制数1的个数是不是确定的？

肯定是确定的是吧 它们的值又不会改变

那么这样子就很简单了

假设里面1的个数是偶数个 那么它这一位最后就会变成0！

因为逢2进1嘛

所以说最后的位数一定是0

又因为是无进位相加

所以说第一位的结果不会影响后面的结果

所以按照这个规律是不是就能推断后面每一位的结果了啊

假如1的个数是偶数 那么最后的结果即使0
假如1的个数是奇数 那么最后的结果就是1

所以说理解了无进位相加 就能很好的理解交换律和结合律了

3. 两个重要结果

N^N = 0

这个很好理解 因为它的位数上的1一定是偶数个的 相加完之后一定等于0

0^N=N

这个也很好理解 因为原来的位数上是1 加上0之后还是1
原来的位数上是0 加上0之后还是0

一. 不使用额外变量交换两个数

要求不使用额外变量 交换a和b的值

交换两个数的值

这个题目算是大家学习编程的入门题了

只要设立一个临时变量tmp就可以了

那么假设题目不让我们使用临时变量 这一题应该怎么做呢？

这里就用异或法来做 只需要三步就好了

	int a = 10;
	int b = 20;
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
1
2
3
4
5

我们来看看结果

成功交换了a b的值

这是为什么呢？

我们来看图

是不是很巧妙的运用了异或的交换律和结合律还有两个重要等式就得到了结果啊

二. 出现奇数次的数

一个数组中只有一个数出现了奇数次 其他所有数都出现了偶数次 要求我们出现奇数次的这个数的值

奇数次 偶数次 听着是不是特别熟悉啊

这是不是我们前面经常提起的

偶数次相同的数异或最后肯定是0！

奇数相同的数字异或最后得到的结果一定是它自身
（因为前面偶数次异或后都是0了 0异或自身等于自身）

所以说代码表示也很简单

int main()
{
	int arr[] = { 1,2,2,3,3,3,3,4,4,5,5,6,6,1,8,10,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	int eor = 0;
	for ( i = 0; i < sz; i++)
	{
		eor ^= arr[i];
	}

	cout << "找到了 单身狗是：" << eor;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们这里能够得到的结果是

三. 如何将一个int整型提取出一个1出来

这里直接给出一个公式

	int a = 10;
	int firstone = a & ((~a) + 1);
1
2

这里简单给大家解释下 不理解的话可以画图再看看

a & (~a)
1

首先 如果a&（~a）最后的结果一定是0是吧

但是呢 假设a的前四位都是0第五位是1

按位取反之后是不是前四位都变成1 第五位变成0了

我们这个时候加个1 是不是就把前面的四个1 怼到第五位去了啊

那之后我们再按位与一下 是不是就只剩下第五位的1了？

四. 数组中两个数出现奇数次

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

这个题目我以前以及写过解法了 这里就不再赘述

大家可以参考我的这篇博客

数组中数字出现的次数

五. 求二进制中1的个数

这道题目其实以前也出现过一次

这里先给出博主以前的解法

int get_count1(int x)
{
	int count = 0;
	while (x)
	{
		x = x & (x - 1);
		count++;
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = get_count1(n);
	printf("%d\n", ret);
	return 0;
}

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

那么我们现在学习了第三题之后能不能想出来最新的解法呢？

当然可以

我们每次将它最前面的1找出来

然后消掉这个1 （按位异或）

不断循环 是不是最后就数位0的时候就能够得到1出现的次数啊

代码表示如下

int get_count1(int x)
{
	int count = 0;
	int rightone = 0;
	while (x)
	{
		rightone = x & ((~x) + 1);
		x ^= rightone;
		count++;
	}
	return count;
}

int main()
{
	int count = 0;
	int x = -1;
	count = get_count1(x);
	cout << "1出现的次数是：" << count << endl;

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

整体表示如下

总结

本文较为详细的介绍了异或在算法中的使用
由于作者水平有限 所以博客中难免会出现纰漏 希望大佬们看到之后可以指正！
最后如果对大家有帮助的话请别忘了多多点赞三连啊
阿尼亚 哇酷哇酷！