感受异或的神奇

原创

小哥 2年前 (2023-05-24) 阅读数 32 #大杂烩

转自：https://www.lijinma.com/blog/2014/05/29/amazing-xor/

什么是异或？

Wikipedia的解释：

在逻辑学中，逻辑算符异或（ exclusive or ）它是两个操作数的逻辑析取类型，符号为 XOR 或 EOR 或 ⊕（常用于编程语言） ^ ）。但与一般逻辑 OR 不同，仅当两个操作数中的一个操作数的值为真而另一个操作数的值不为真时，XOR 运算符的值才为真。转化为一个命题是：“两者的价值观不同”或“有，只有一个是真的”

定义：

1 ⊕ 1 = 0

0 ⊕ 0 = 0

1 ⊕ 0 = 1

0 ⊕ 1 = 1

真值表：

B = 0

B = 1

A = 0

A = 1

表达式：

Y = A’ · B + A · B’

说明：我使用 · 作为 与 ，我使用 + 作为 或 ，我使用作为 否 (它应该被使用 头上一横 但是编辑起来太难了，所以我用了它）；

异或的特点是什么？

根据定义，我们可以轻松获得 异或 两个特点：

恒等律： X ⊕ 0 = X 归零律： X ⊕ X = 0

然后我们使用 真值表 可以证明：

（1）交换律

1 2 3

A ⊕ B = A · B + A · B

B ⊕ A = B · A + B · A

因为 ·与 和 +或 两个运算满足交换定律，因此：

A ⊕ B = B ⊕ A

（2）结合律

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

(A ⊕ B) ⊕ C

= (A · B + A · B) ⊕ C

= (A · B + A · B) · C + (A · B + A · B) · C 

= ((A · B) · (A · B))· C + A · B · C  + A · B · C 

= ((A + B) · (A + B))· C + A · B · C  + A · B · C 

= (A · B + A · B) · C + A · B · C  + A · B · C 

= A · B · C + A · B · C + A · B · C  + A · B · C

你可以用同样的推导方法推导（请允许我偷懒，打数学公式不容易） +_+）：

1 2 3

A ⊕ (B ⊕ C)

= A · B · C + A · B · C + A · B · C  + A · B · C

在证明过程中使用了以下方法（ ·与 +或 否 ）：

·与 +或 交换律：

1 2 3

A · B = B · A

A + B = B + A

·与 +或 结合律：

1 2 3

(A · B) · C = A · (B · C)

(A + B) + C = A + (B + C)

·与 +或 分配律：

1 2 3

A · (B + C)= A · B + A · C

A + B · C = (A + B) · (A + C)

摩尔定理：

1 2 3

(A · B) = A + B

(A + B) = A · B

结论：

交换律： A ⊕ B = B ⊕ A 结合律： A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C

有了 归零率 和 结合律 我们可以很容易地证明：

自反： A ⊕ B ⊕ B = A ⊕ 0 = A

也许这些特征会被自然地理解，但是如果你正在解决问题，你可能会忘记异或的这些特征。因此，适当的应用可以加深我们对异或的理解;

1 2 3 4

A ⊕ 1 = A;
A ⊕ 0 = A;
A ⊕ A = 0;
A ⊕ A = 1;

异或有什么神奇之处（应用）？

说明：以下内容 异或 使用所有符号 ^

也许你对混乱的公式和计算有点恼火，这不就是一个简单的异或运算吗？解释还是那么复杂，呵呵，别担心。一旦你奠定了基础，你就会站在巨人的肩膀上。让我们踏上异或的神奇之旅;

（1）快速比较两个值

让我们从一个简单的问题开始;法官二int数字a，b无论相等与否，你一定会想到评判 a - b == 0 但如果我们判断 a ^ b == 0 效率会更高，但为什么更高？让我们把它作为家庭作业给你，并考虑如何实现减法; 一起来看看吧ipv6比较在;

1 2 3 4 5 6 7

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执行 XOR 将导致与原始值相反的结果;

0 ^ 1 = 1

1 ^ 1 = 0

例如：翻转 10100001 的第6位，答：您可以将此数字与 00100000 执行按位异或运算; 10100001 ^ 00100000 = 10000001

我们提供了一个常用的代码：

1 2 3

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磁盘的数据。

RAID5的实现比上面的描述要复杂得多，但原理是使用异或，感兴趣的同学，看看 RAID5

（6）经典标题：不使用其他空格交换两个值

1 2 3

a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;

这个问题不用解释，太流行了，哈哈，但是很好用 异或 的特性；

（7）面试问题：交换二进制数的奇偶位;

题目编写宏定义以实现集成int例如，交换一类数字的奇数和偶数位6的2进制为 00000110 ，(从右向左)第一和第二位置可互换，第三和第四位置可互换，其余的0无需交换，获得 00001001 输出应为9；

思路我们可以将问题分为三个步骤（这也是一种分而治之的方法吗 -。-）第一步是根据原始值的偶数得到目标值的奇数位，将不需要的数字重置为零;第二步是根据原值的奇数得到目标值的偶数，将不需要的数字复位为零;步骤3：将上面提到的两个不完整的目标值合并为一个完整的目标值;

代码为：

1 2 3 4 5 6 7 8 9

//假设 int 占用两个字节，16位；
#include
#include
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做一个AND操作，移位后只保留偶数位值，所有奇数都是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.最后，执行OR操作（加法）得到1001。

（7）最最常出现的面试题在整数数组中，除了N个数字之外，其他的数字都出现了两次，找出这N个数字；

比如，从 {1, 2, 3, 4, 5, 3, 2, 4, 5} 在以下位置查找单个数字： 1

让我们从最简单的，找一个数字开始；

题目：（LeetCode 通过率最高的问题 Single Number: Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 思路：当你得到这个问题时，你会本能地使用排序（我们经常需要对数字文本进行排序）。排序后，您可以确定数字是否成对显示。这个想法很明显，但排序算法的上限是 O(nlogn)，不符合问题的要求;

学得很强大 异或 我们可以轻松地使用它的功能来完成这个问题：（1）A ^ A = 0; （2）异或满足交换和结社规律; 所有假设都有数组： A B C B C D A 使用异或：

1 2 3 4 5

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) ；

代码：

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

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;
    }
};

接下来，让我们增加一些难度：

题目在整数数组中，除了 两 除数字外，所有其他数字都会出现两次。请编写一个程序来查找这两个只出现一次的数字？

思路：第一步：它与我们上面的解决方案绝对相同，使用所有数字 异或 但最终的结果是 a 和 b（假设 a 和 b 两个值（单个数字）的异或结果 aXORb未直接获得 a 和 b 的值；

第二步：想办法获取它 a 或者 b，假设 aXORb 为 00001001 （F肯定不为0），根君 aXORb 我们发现， 值为1的位 （例如，从右到左的第一个位置）表示它处于此位置 a 和 b 的值不同;因此，基于此特征，我们将所有第一个确定为1通过 XOR 的数量，结果是 a 或者 b；

第三步：aXORb = a ^ b假设我们已经找到了它 a，根据 异或 特征，我们知道，b = aXORb ^ a；所以我们可以找出答案 b；所以我们只需要循环两次;

所以我们的时间复杂度是 O(n)空间复杂度为 O(1) 代码：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include 
#include 
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;
}

接下来，让我们添加一些难度：

题目在整数数组中，除了 三 除数字外，所有其他数字都会出现两次。请编写一个程序来查找这两个只出现一次的数字？

思路：

第一步：它与我们上面的解决方案绝对相同，使用所有数字 异或 但最终的结果是 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在位置之后，执行 XOR 并将低阶的第一个数字作为1您可以在三者中找到“一个不同”的低位，第一个数字是1的位置，假设此值为 firstOneBit。
遍历这三个数字(aXORbXORc ^ a)、(aXORbXORc ^ b) 和 (aXORbXORc ^ c)如果找到一定数量的异或 aXORbXORc 等于 firstOneBit这个数字是“一个不同”的数字;
找到一个数字后，我们可以使用上述方法找到剩下的两个数字;

第三步完成简化问题的第二步后，我们回到我们的问题。我们的问题比简化问题多了一对干扰数据，我们可以使用 XOR 来删除干扰数据（请记住，我们对这个问题使用 XOR）i删除干扰数据;

所以我们的时间复杂度仍然是 O(n)空间复杂度为 O(1)

代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

#include 
#include 
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;
}

我参考了教科书离散数学和应用以及其他几个博客编写了此文档。如果我参考您的博客但没有注明来源，请与我联系并告诉我是否有错误。我希望你能指出来，希望你能有更多的补品。谢谢。

参考：

http://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96

http://yjq24.blogbus.com/logs/41863963.html

http://wzw19191.blog.163.com/blog/static/131135470200992610551971/

http://kapok.blog.51cto.com/517862/129941

http://blog.csdn.net/huxian370/article/details/8024416

http://www.cnblogs.com/Ivony/archive/2009/07/23/1529254.html

http://blog.chinaunix.net/uid-20937170-id-3407361.html

http://blog.csdn.net/yfkiss/article/details/11775569

http://blog.sina.com.cn/s/blog_88c9ddc50101810p.html

http://blog.csdn.net/pathuang68/article/details/7567027