异或的性质
- a^a=0；
- a^0=a;
- a^b=b^a，即交换律；
入门问题
问题描述
有一组数据，其中某些数据出现两次，只有一个数据出现过一次，请找出它。如：
arr[] = {1, 4, 2, 2, 4};
// 结果应为1
解决方法
由上面异或的性质，可以这样做：将所有元素进行异或，其结果就是出现一次的那个数。
void find_number_v1()
{
int arr[] = {3, 4, 5, 9, 3, 5, 4};
int i, target = 0;
for (i = 0; i < sizeof(arr)/sizeof(int); ++i) {
target = target ^ arr[i];
}
printf("target = %d\n", target);
// 3出现4次，异或为0；4出现2次，异或为0；1出现3次，异或为1；
int arr2[] = {3, 3, 1, 4, 3, 4, 3, 1, 1};
target = 0;
for (i = 0; i < sizeof(arr2)/sizeof(int); ++i) {
target = target ^ arr2[i];
}
printf("target = %d\n", target);
}
问题延伸
只要保证目标数据出现的次数是奇数次，其它数据出现的次数是偶数次都可以根据这种方法找出目标数据；
进阶问题
问题描述
还是一组数据，有些数据出现两次，有两个不同的数据只出现一次，请找出这两个数据（A和B）。
解决方法
可以把数据分为两组，将A和B分到不同的组，然后再按第一种方法找出来给你个数据。可是如何将A，B分到不同的组中去呢？
一般想法都是这样的：找到A和B之间的一个数C，然后大于C为一组，小于C为另一组，这样A和B就被分开。但是现在A和B都不知道啊？怎么办呢？只要找到一个A，B的不同点即可，这样就可以区分A和B。是否可以从两个数异或的结果C中找到标识这两个数不同的特点呢？答案是可以的。
- C是A和B异或的结果，为的地方说明两者的不同之处，我们只需要找到一个不同点即可；
- 从右至左，找到C中第一位不为0的位置，记为，说明A和B在第位不相同；
- 截取从第0位到第位，组成一个数D；
- 用数D通过相与的方法就可以区分A和B了，一个结果比为0，一个结果为1。
如：
// A = 5 = 1001
// B = 2 = 0010
// D = A^B = 1011
// E = 1
// A&E = 1
// B&E = 0
// 这样就把A和B分开了，其它数据被分到那一组不重要，因为是成对的，最终可以被异或为0。
代码实现：
void find_number_v2()
{
// 目标数是8和2
int arr[] = {12, 3, 8, 3, 4, 9, 10, 9, 4, 10, 12, 2};
int pivot = 0;
unsigned int i = 0;
// 1. 得到整组数据的异或值
for (i = 0; i < sizeof(arr)/sizeof(int); ++i) {
pivot = pivot ^ arr[i];
}
i = 0;
// 2. 找到pivot第一位不为0的位置
while(!(pivot & (1 << i))) {
i++;
}
// 3. 将第一位不为0的右边取出，作为pivot（此pivot可以区分A和B）
pivot = (1 << i);
// 4. 将A和B分到两个不同的组，其它的数据都是成对的，无所谓
for (i = 0; i < sizeof(arr)/sizeof(int); ++i) {
// pivot&arr[i] >= 1
if (pivot&arr[i]) {
//left[] = arr[i];
printf("L:>>arr[%d]=%d\n", i, arr[i]);
} else {
//right[] = arr[i];
printf("\t\t\tR:>>arr[%d]=%d\n", i, arr[i]);
}
}
// 5. 然后再对left和right分别用异或即可得出两个不同的数字。
}
再对两组数据的所有元素进行异或即可。
问题延伸
只要保证其它数据出现偶数次即可，那两个数出现奇数次即可。
如果要有3个不同的数呢？
交换两数
/**
* 主要原理：
* a = a ^ b; //找到a和b不相同的bit，并且这些bit都是1
* b = a ^ b; //那么b就等于把a与b不同的位置取反
* a = a ^ b; //现在b等于a了，那么a就等于把b与a不同的位置取反
* 1. 把a和b都展开成bit的形式
* 2. 找到a和b的bit不同的位置，这些位置都被置为1
* 3. 把a与b不同的位置取反就是b，同理也是一样的
* a = 4 = 0100;
* b = 8 = 1000;
*
* a = a^b = 1100; //a和b不同的就是bit2和bit3
* b = a^b = 0100; //b就等于把a的bit2和bit3取反，由于bit2和bit3都为1，所以异或=取反
* a = a^b = 1000; //同理
*
* 优点：速率快，不需要其它作为temp
* 缺点：只能用于整形，浮点型进行转换的话会有误差。
* @Author CofCai
* @DateTime 2021-01-04T20:21:27+0800
*/
void swap_two_num()
{
int a = 10, b = -151;
a = a^b;
b = a^b;
a = a^b;
printf("a = %d\tb = %d\n", a, b);
float x = 10.2, y = 203.23;
x = x*100;
y = y*100;
x = (int)(x)^(int)(y);
y = (int)(x)^(int)(y);
x = (int)(x)^(int)(y);
printf("x = %f\ty = %f\n", x/100, y/100);
}
对于上面的缺点（只能转换整形数），其实是可以解决的。因为浮点数在计算机存储的还是二进制形式，而异或的对象就是二进制形式，所以原理上还是可以通过异或交换两个数。
#include <stdio.h>
#include <stdlib.h>
// 如果传入的x、y是char类型，那么结果会有问题，因为char类型
// 转为int类型，字节数增加，增加的字节的内容是未知的。
// 所以，要保证x、y的字节数和int类型所占的字节数相等。
// char类型的可以直接异或，即c = c1^c2是不会报错的。
#define SWAP_NUM(x, y) ({ \
*(int*)(&x) = *(int*)(&x) ^ *(int*)(&y); \
*(int*)(&y) = *(int*)(&x) ^ *(int*)(&y); \
*(int*)(&x) = *(int*)(&x) ^ *(int*)(&y); \
})
int main(int argc, char const *argv[])
{
char c1 = '2', c2 = 'a';
int a = 7455, b = 23;
float m = 2.32, n = -77.23;
c1 = c1^c2;
c2 = c1^c2;
c1 = c1^c2;
printf("c1 = %c, c2 = %c\n", c1, c2);
SWAP_NUM(a, b);
printf("a = %d, b = %d\n", a, b);
SWAP_NUM(m, n);
printf("m = %f, n = %f\n", m, n);
return 0;
}
