因为未知，所以全力以赴
目录
例1.实现两个数的交换
例2.找出单身狗
1.简单版
2.进阶版
大家好，我是纪宁。这篇博客介绍^操作符及使用案例。
位操作符是对操作数的二进制补码进行操作。^就是位操作符的一种，叫按位异或操作符。计算结果是对应操作数的二进制位相同为0，相异为1。
位操作符中也有一些类似于加减法中的一些运算法则，如一个数按位异或0就得到这个数本身，一个数和它自己进行按位异或得到0，同样按位异或的运算也支持交换律，如：a^b^a=a^a^b。
例1.实现两个数的交换
这是一道变态的面试题：
不能创建临时变量（第三个变量），实现两个数的交换
在未学习按位异或操作符之前，我们可能会想到下面的方法：
int a = 2;
int b = 3;
printf("交换前:a = %d, b= %d\n", a, b);
a = a + b;
b = a - b;
a = a - b;
printf("交换后:a = %d, b= %d", a, b);
这种方法在一般情况下是可以得出正确结果得，但是当a,b非常大时，a+b可能会超过存储范围，就会截断，上述代码可能会溢出。
用按位异或的方法可以非常巧妙地解决溢出问题。
#include <stdio.h>
int main()
{
int a = 10;
int b = 20;
a = a ^ b;
b = a ^ b;
a = a ^ b;
printf("a = %d b = %d\n", a, b);
return 0;
}
因为 a^a=0，a^0=a，所以a^b^a=a^a^b=0^b=b，同样b^a^b=a。巧妙实现了a和b的交换
例2.找出单身狗
1.简单版
有一个数组只有一个数组出现一次，其余数字都是成对出现的，请找出只出现一次的数字
如 1 2 3 4 5 1 2 3 4，其中的单身狗就是 5
思路就是将数组里面所有的数字进行按位异或运算，因为异或支持交换律，且相同数字按位异或结果为0，因为只有一个‘单身狗’，所以按位异或的结果就是‘单身狗’。
int find_single_dog1(int arr[], int sz)
{
int i = 0;
int ret = 0;
for (i = 0; i < sz; i++)
{
ret ^= arr[i];
}
return ret;
}
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
int dog = find_single_dog1(arr, sz);
printf("%d\n", dog);
return 0;
}
2.进阶版
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。例如，有数组的元素是：1，2，3，4，5，1，2，3，4，6 。只有5和6只出现1次，要找出5和6。
找出两个‘单身狗’的思路是，将两个单身狗分到两个组中，每组除了单身狗外还有一组或者多组成对出现的数。那么，如何分组，就成了找出‘单身狗’的关键。
先将数组中所有数按位异或，因为其他的数字都是成对的，根据按位异或的交换律和相同数字按位异或结果为0得出，所有数字按位异或的结果，就是两个‘单身狗’按位异或的结果。
找出这个结果中从最低位开始最先出现1的那一位，根据按位异或的规则，相异为1，所以这一个二进制位就能成为分组的关键。
每个数字都对这一个二进制位进行判断，0/1，分为两个组，同时，将单身狗也分在了两个组中，也就找到了‘单身狗’。
#include<stdio.h>
void find_single_dog2(int arr[], int sz, int* s1, int* s2)
{
int i = 0;
int ret = 0;
for (i = 0; i < sz; i++)
{
ret ^= arr[i];
}
int pos = 0;
for (i = 0; i < 32; i++)
{
if (((ret >> i) & 1) == 1)
{
pos = i;
break;
}
}
for (i = 0; i < sz; i++)
{
if (((arr[i] >> pos) & 1) == 1)
(*s1)^= arr[i];
}
*s2 = ret^(*s1);
}
int main()
{
int arr[10] = { 1,2,3,4,5,1,2,3,4,6 };
int dog1 = 0;
int dog2 = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
find_single_dog2(arr, sz, &dog1, &dog2);
printf("dog1:%d,dog2:%d", dog1, dog2);
return 0;
}
博主写了好长时间，如果你能给博主一个免费三连鼓励一下博主的话，那么我觉得你的真是 泰 裤 辣 ！！！
————————————————
