异或运算的一些应用

定义

　　异或是一个数学运算，用于逻辑运算。如果a、b两个值不同，则异或结果为1，否则结果为0，在C语言中是一种强大的基本运算符，有很多巧妙的应用。

　　例如, A = 14, B = 10;

　　A = 14，二进制则为1110，B = 10，二进制为1010.

　　对二进制数进行异或运算 -> 1110^1010 = 0100，对应十进制就为4。

　　在二进制数异或过程中，我们可以得知异或运算是一种半加运算。什么意思呢？半加即不带进位的加法运算。

　　如上面1110^1010 = 0100，如果在加法中，如下

　　我们从低位开始加起，首先第0位为0+0=0；第一位1+1=0，如果是加号运算符，则需要进位，但由于是异或运算（半加），故不用进位，第二位为1+0=1；最后一位为1+1=0。最终结果就是0100，这就是半加的过程。

特性

　　1.一个数与0进行异或运算，其运算结果是自身；

　　2.一个数与自身进行异或运算，其运算结果为0；

　　3.异或运算满足分配律，即 3^4^3与3^3^4的结果一样，都为4。

异或运算的一些应用

1.异或最常用的一种用法 -- 交换两个数的值。

　　这里直接上代码。

 1 /*************************************************************************
 2     > File Name: swap.c
 3     > Author: yudongqun
 4     > Mail: qq2841015@163.com
 5     > Created Time: Fri 16 Oct 2020 04:48:54 PM CST
 6  ************************************************************************/
 7 
 8 #include <stdio.h>
 9 
10 int main(void) {
11     int a = 10, b = 20, tmp;
12 
13 #if 0
14     /*用中间值来实现值交换*/
15     tmp = a;
16     a = b;
17     b = tmp;
18 #else
19     /*用异或操作来实现值交换*/
20     a ^= b;
21     b ^= a;
22     a ^= b;
23 #endif
24     printf("a: %d, b: %d
", a, b);
25 
26     return 0;
27 }

ydqun@VM-0-9-ubuntu operator % gcc swap.c                                                                  [0]
ydqun@VM-0-9-ubuntu operator % ./a.out                                                                     [0]
a: 20, b: 10
ydqun@VM-0-9-ubuntu operator %

　　这里异或操作实现的值交换的好处是少使用了一个临时变量，执行效率也比较高。

2，寻找只出现一次的数字。

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

 1 /*************************************************************************
 2     > File Name: single_number.c
 3     > Author: yudongqun
 4     > Mail: qq2841015@163.com
 5     > Created Time: Fri 16 Oct 2020 05:20:25 PM CST
 6  ************************************************************************/
 7 
 8 #include <stdio.h>
 9 
10 int single_number(int nums[], int n) {
11     int res = 0;
12     for (int index = 0; index < n; index++) {
13         res ^= nums[index];
14     }
15     return res;
16 }
17 
18 int main(void) {
19     int nums[5] = {1, 2, 2, 1, 6};
20     printf("single number is : %d
", single_number(nums, 5));
21 }

ydqun@VM-0-9-ubuntu operator % g++ single_number.c                                                         [0]
ydqun@VM-0-9-ubuntu operator % ./a.out                                                                     [0]
single number is : 6
ydqun@VM-0-9-ubuntu operator %

　　这里是运用了异或的特性2与特性3，1^2^2^1^6 = 1^1^2^2^6 = 0^0^6 = 6。