1.异或：相同为假（0），相异为真（1）
2. 基本运算：
1 ⊕ 1 = 0
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
3.两个特性：
恒等律——X ⊕ 0 = X
归零律——X ⊕ X = 0
同样的可以用真值表证明交换律，结合律，分配律。
4.异或的应用
（1）快速比较两个值
static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
{
return (((a1->s6_addr32[0] ^ a2->s6_addr32[0]) |
(a1->s6_addr32[1] ^ a2->s6_addr32[1]) |
(a1->s6_addr32[2] ^ a2->s6_addr32[2]) |
(a1->s6_addr32[3] ^ a2->s6_addr32[3])) == 0);
}
（2）在汇编语言中经常用于将变量置零：xor a，a；
（3）可以使用异或使某些特定的位翻转，因为不管是0或者是1，与1做异或都将得到原值的相反值；
0 ^ 1 = 1
1 ^ 1 = 0
例如：翻转10100001的第6位， 答案：可以将该数与00100000进行按位异或运算;10100001 ^ 00100000 = 10000001
以下是常用的一段代码：
unsigned int a, b, mask = 1 << 6; a = 0xB1; // 10100001 b = a ^ mask; /* flip the 6th bit */
（4）使用异或判断一个二进制数中1的数量是奇数还是偶数
例如：求10100001中1的数量是奇数还是偶数； 答案：1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1，结果为0就是偶数个1； 应用：这条性质可用于奇偶校验（Parity Check），比如在串口通信过程中，每个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位粗略地判断接收到的数据是否有误
（5）校验与恢复
校验和恢复主要利用的了异或的特性：IF a ^ b = c THEN a ^ c = b
应用：一个很好的应用实例是RAID5，使用3块磁盘（A、B、C）组成RAID5阵列，当用户写数据时，将数据分成两部分，分别写到磁盘A和磁盘B，A ^ B的结果写到磁盘C；当读取A的数据时，通过B ^ C可以对A的数据做校验，当A盘出错时，通过B ^ C也可以恢复A盘的数据。
（6）不使用其他空间，交换两个值（经典题目）
a = a ^ b; b = a ^ b; //a ^ b ^ b = a ^ 0 = a; a = a ^ b;
（7）互换二进制数的奇偶位（面试题）
题目：写一个宏定义，实现的功能是将一个int型的数的奇偶位互换，例如6的2进制为00000110，(从右向左)第一位与第二位互换，第三位与第四位互换，其余都是0不需要交换，得到00001001，输出应该为9；
思路：我们可以把我们的问题分为三步（类似分治法），第一步，根据原值的偶数位获取到目标值的奇数位，并把不需要的位清零；第二步，根据原值的奇数位获取到目标值的偶数位，并把不需要的位清零；第三步：把上述两个残缺的目标值合并成一个完整的目标值；
代码为：
//假设 int 占两个字节，16位；
#include<iostream>
#include<string>
using namespace std;
#define N(n) ((n<<1)&(0xAAAA))|((n>>1)&(0x5555))
void main(){
int k = N(6);
cout << k << endl;
}
解释： 1.为简化说明，我们以4位二进制码为例，0xAAAA 我们用 1010 代替；0x5555 我们用 0101 代替； 2.(n<<1)&(1010) 把n先左移1位，再与1010做与运算，只保留移位之后的偶数位的值，奇数位全为0，实际上是只保留了n的奇数位的值，并把它们交换到了偶数位上。比如 n = 0110 , n<<1 = 1100, (n<<1) & 1010 = 1000 ; 3.(n>>1)&(0101) 把n右移一位，再与 0101 做与运算，只保留移位之后的奇数位的值，偶数位全为0，实际是只保留n 的偶数位的值，并把它们交换到对应的奇数位上。n = 0110； n>>1 = 0011； (n>>1) & 0101 = 0001； 4.最后做或运算（相加），得到1001。
（8）一个整型数组里除了N个数字之外，其他的数字都出现了两次，找出这N个数字（面试题）
学习了强大的异或，我们可以轻松的使用它的特性来完成这道题目： （1）A ^ A = 0; （2）异或满足交换律、结合律； 所有假设有数组：A B C B C D A 使用异或：
A ^ B ^ C ^ B ^ C ^ D ^ A = A ^ A ^ B ^ B ^ C ^ C ^ D = 0 ^ 0 ^ 0 ^ D = 0 ^ D = D
时间复杂度为O（n)，空间复杂度为O（1)
代码：
class Solution {
public:
int singleNumber(int A[], int n) {
//特殊情况1,2
if(n<=0) return -1;
if(n==1) return A[0];
int result = 0;
for (int i = 0; i < n; i ++) {
result = result ^ A[i];
}
return result;
}
};
（8）变式：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字？
思路： 第一步：肯定还是像我们上面的解法一样，所有数进行异或，不过最终得到的结果是 a 和 b（假设 a 和 b 是落单的数字）两个值的异或结果 aXORb，没有直接得到 a 和 b 的值；
第二步：想办法得到 a 或者 b，假设 aXORb 为 00001001（F肯定不为0），根君 aXORb 的值我们发现，值为1的位（比如从右向左第一位）表示在此位上 a 和 b 的值不同；所以，根据这个特点，我们找出来所有第一位为1的数进行异或，得到的就是 a 或者 b；
第三步：aXORb = a ^ b，假设我们已经找到了 a，根据异或特性，我们知道，b = aXORb ^ a；这样我们就可以找出 b；所以我们只需要循环两次；
#include <iostream>
#include <assert.h>
using namespace std;
int getFirstOneBit(int num) //输出 num 的低位中的第一个 1 的位置
{
return num & ~(num - 1); // num 与 -num 相与找到
}
void findTwo(int *array, int length){
int aXORb = 0;
int firstOneBit = 0;
int a = 0;
int b = 0;
for (int i = 0; i < length; i++) {
aXORb ^= array[i];
}
assert(aXORb != 0); //保证题目要求，有两个single的数字
firstOneBit = getFirstOneBit(aXORb);
for (int i = 0; i < length; ++i) {
if(array[i] & firstOneBit) {
a ^= array[i];
}
}
b = aXORb ^ a;
cout << "a: " << a << endl;
cout << "b: " << b << endl;
}
int main()
{
int array1[] = {2, 5, 8, 2, 5, 8, 6, 7};
findTwo(array1, 8);
return 0;
}
时间复杂度为O（n)，空间复杂度为O（1）
（8）变式2：一个整型数组里除了三个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字？
思路：
第一步：肯定还是像我们上面的解法一样，所有数进行异或，不过最终得到的结果是 a、b 和 c（假设 a、b 和 c 是落单的数字）三个值的异或结果 aXORbXORc，没有直接得到 a、b 和 c 的值；
第二步：想办法得到 a、b 和 c 中的一个，让偶们把问题简化一下；
假设一个数组中有3个不同的数字 a、b 和 c，已知 aXORbXORc = a ^ b ^ c ，求 a、b 和 c 。
思路： 1. 根据题目 aXORbXORc ^ a = b ^ c; aXORbXORc ^ b = a ^ c; aXORbXORc ^ c = a ^ b; 因为：(b ^ c) ^ (a ^ c) ^ (a ^ b) = 0; 所以：(aXORbXORc ^ a) ^ (aXORbXORc ^ b) ^ (aXORbXORc ^ c) = 0;
-
下一步是关键： 假设 X ^ Y ^ Z = 0，则 X Y Z 三个数的低位第一位为1的位置两个相同，一个不同； 比如 X: 00001000, Y: 00000100, Z: 00001100 Y和Z的低位第一位都是00000100， X的低位第一位是00001000； 这一步可以使用倒推法证明： 已知：三个数的低位第一位为1的位置有三种情况，一种就是全相同，一种就是两个不同，一个不同，一种就是三个不同； （1）如果是全相同，则 X ^ Y ^ Z != 0 (1 ^ 1 ^ 1 = 1)，与前提X ^ Y ^ Z = 0矛盾，不成立； （2）如果三个不同，则 X ^ Y ^ Z != 0 (1 ^ 0 ^ 0 = 1)，与前提X ^ Y ^ Z = 0矛盾，不成立； 所以结果是：两个不同，一个不同
-
(aXORbXORc ^ a) ^ (aXORbXORc ^ b) ^ (aXORbXORc ^ c) = 0; 所以三个数(aXORbXORc ^ a)、(aXORbXORc ^ b) 和 (aXORbXORc ^ c) 的低位第一位为1的位置两个相同，一个不同；那么我们获取到这三个数的低位第一位为1的位置后，进行异或并取低位第一位为1的位置，就可以找到三个中“一个不同”的低位第一位为1的位置，假设这个值为 firstOneBit。
-
遍历这三个数(aXORbXORc ^ a)、(aXORbXORc ^ b) 和 (aXORbXORc ^ c)，如果发现某个数异或 aXORbXORc 等于 firstOneBit，这个数就是“一个不同”的那个数；
-
找到了一个数，剩下的两个数，我们就可以通过上面的方法找出来；
第三步：完成了第二步的简化题，我们回到我们的问题，我们的问题比简化的问题多了一个成对的干扰数据，我们可以使用异或要去除干扰数据（记住，我们这个题目都是用异或i去除干扰数据的）；
#include <iostream>
#include <assert.h>
using namespace std;
int getFirstOneBit(int num) //输出 num 的低位中的第一个 1 的位置
{
return num & ~(num - 1); // num 与 -num 相与找到
}
void findTwo(int *array, int length){
int aXORb = 0;
int firstOneBit = 0;
int a = 0;
int b = 0;
for (int i = 0; i < length; i++) {
aXORb ^= array[i];
}
assert(aXORb != 0); //保证题目要求，有两个single的数字
firstOneBit = getFirstOneBit(aXORb);
for (int i = 0; i < length; ++i) {
if(array[i] & firstOneBit) {
a ^= array[i];
}
}
b = aXORb ^ a;
cout << "a: " << a << endl;
cout << "b: " << b << endl;
}
int findOne(int *array, int length) {
int aXORbXORc = 0;
int c = 0;
int firstOneBit = 0;
for (int i = 0; i < length; ++i) {
aXORbXORc ^= array[i];
}
for (int i = 0; i < length; ++i) {
firstOneBit ^= getFirstOneBit(aXORbXORc ^ array[i]); //使用异或会排除掉不相干的元素
}
// firstOneBit = getFirstOneBit(a ^ b) ^ getFirstOneBit(a ^ c) ^ getFirstOneBit(b ^ c);
firstOneBit = getFirstOneBit(firstOneBit); //获取到最低位下面要用
for (int i = 0; i < length; ++i) {
if (getFirstOneBit(aXORbXORc ^ array[i]) == firstOneBit) {
c ^= array[i]; //使用异或会排除掉不相干的元素
}
}
cout << "c: " << c << endl;
return c;
}
int main()
{
int array1[] = {2, 5, 8, 2, 5, 8, 6, 7, 1};
int c = findOne(array1, 9);
int array2[] = {2, 5, 8, 2, 5, 8, 6, 7, 1, c}; //为了更好重用函数，我重新定义了一个数组让大家理解
findTwo(array2, 10);
return 0;
}
标签：addr32,运算,int,异或,num,aXORbXORc,aXORb From： https://www.cnblogs.com/yhstsy/p/16714842.html