一文搞懂 位运算 异或（Java实现）_java里异或怎么实现的

        提起异或想必很多小伙伴们既熟悉又陌生，熟悉是因为好像在离散数学或者学某个编程语言

时听过这个东西，而陌生呢，则是因为自己平时并没有用过，以至于当在某个场景 （我猜是在看

题解或者某篇博客时）  看到这个名词的时候很懵逼，因此才会幸运地看到这里，那么请继续往下

看吧。

---

目录

一. 什么是异或呢？

二. 异或有哪些运算法则呢？(不用背，下面会有例子帮助理解) 

三.计算机底层是怎么进行异或运算的呢？

四.异或有什么妙用？

1. 我们来看一道leetcode上的题目

2. 两个数字交换

3. 两个数字判等

4. 加密

5. 备份

五.最后的话

 

 

一. 什么是异或呢？

 

        异或是位运算的一种，属于逻辑运算符，是一种二进制运算。在计算机中用符号XOR 或 ^ 来

表示，数学中则用 ⊕ 表示。

        众所周知，程序中的所有数据在计算机内存中都是以二进制的形式存储的。因此异或直接处

理的是二进制数字 0 和 1 。异或最基础的运算法则为: 0 ⊕ 0 = 0，1 ⊕ 0 = 1，0 ⊕ 1 = 1 ，1 ⊕ 1 =

0   一句话简单概括就是  相同为 0 ，不同为 1 。 

---

二. 异或有哪些运算法则呢？(不用背，下面会有例子帮助理解) 

        1. 归零律： a  ⊕  a  = 0   

        2. 恒等律： a  ⊕  0  = a            

        3. 交换律： a  ⊕  b = b  ⊕  a

        4. 结合律： a  ⊕  b  ⊕  c  =  a ⊕ ​​​​​​ ( b  ⊕ ​ ​​​​​​c ) = ( a  ⊕  b )  ⊕ c

        5. 自   反：  a ⊕ b ⊕ a = b

        6.  d = a ⊕ b ⊕ c   可以推出   a  =  d  ⊕  b  ⊕  c.  

---

 

三.计算机底层是怎么进行异或运算的呢？

        现在有三个数字 a b c   其对应的十进制和二进制已经给出

        a = 10= 1010   b = 8 = 1000  c = 12 = 1100 

        我们已经知道计算机内存中以二进制存储数据，因此在进行异或运算时，计算机先把十进制

数字转换为二进制数字再进行相应的运算。如下面的几个例子，计算机一位一位地进行异或运算

（相同为0，不同为1），之后将每一位计算得到的结果合在一起，即是最终结果。

 

        a ⊕ a =     1 0 1 0
                     ⊕ 1 0 1 0
                     =  0 0 0 0

        a ⊕ 0 =     1 0 1 0
                     ⊕ 0 0 0 0
                     =  1 0 1 0

        a ⊕ b =     1 0 1 0
                     ⊕ 1 0 0 0
                     =  0 0 1 0

 

        a ⊕ b ⊕ c  =     1 0 1 0
                                 1 0 0 0
                             ⊕ 1 1 0 0
                             =  1 1 1 0

 

        a ⊕ b ⊕ a  =      1 0 1 0
                                  1 0 0 0
                              ⊕ 1 0 1 0
                              =  1 0 0 0

---

四.异或有什么妙用？

1. 我们来看一道leetcode上的题目

           第136题 只出现一次的数字https://leetcode.cn/problems/single-number/

 这道题是要我们找出来数组中只出现一次的数字

 注意要求：时间复杂度O(n)   空间复杂度O(1) 

1.1 哈希表   （时间复杂度O(n)   空间复杂度O(n) ）

 

        我看到这个题的第一思路就是用哈希表。这是这种题目通用的解法，利用哈希表的特性很容

易区分重复的和不重复的。

         但是此时，时间复杂度O(n)   空间复杂度O(n)   并不满足题目要求 

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //获取当前数组中的数字在哈希表中的个数  如果没有则返回null
            Integer integer = map.get(nums[i]);
            if (integer == null)//当前哈希表中没有该数字
                map.put(nums[i], 1);//加入哈希表中，数量 = 1
            else
                map.put(nums[i], integer + 1);//当前哈希表中已存在该数字，数量+1
        }
        Set<Integer> integers = map.keySet();
        for (Integer integer : integers) {
            //获取当前哈希表中各个数字的个数  个数为 1 的话即为所求。
            if (map.get(integer) == 1)
                return integer;
        }
        return -1;
    }
}

 

1.2 暴力双重循环    （时间复杂度O(n2)   空间复杂度O(1) ）

        然后就想到暴力的方式了，但是要用到两重循环 ，这个时候的时间复杂度就是 O(n2) 了，也

不满足要求。

此处代码省略

1.3 快排    （时间复杂度O(nlogn)   空间复杂度O(1) ）

        去看题解发现还可以先排序，然后再遍历找第 i 个数字和第 i + 1 个数字不相同的，当然此处

遍历的时候就是 i = i + 2   而不是 i++ 了，但是排序算法中没有 时间复杂度是O(n) 的，即便是快速

排序，其时间复杂度也是O(nlogn) ，因此也解决不了问题

        for(int i=0;i<nums.length;i+=2){
            //
        }

 1.4 异或     （时间复杂度O(n)   空间复杂度O(1) ）

        用异或来解决这个问题就很美妙了。

class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        if (nums.length > 1) {
            for (int i = 1; i < nums.length; i++) {
                //循环结束后ans 就等于数组中所有元素异或后的结果
                ans = ans ^ nums[i];
            }
        }
        return ans;
    }
}

        我们能够看到用异或来处理这个问题效率尤其的高。不需要像哈希表那样占用额外的空间，

也不用双重循环。真是优雅之极。

        可能有的小伙伴不理解为什么要用异或解决这个问题，异或是怎么解决这个问题的。下面我

们就来好好说说异或处理这样的问题的美妙之处。

        首先由前面我们已经知道，异或处理两个相同的数据时，得到的结果为0，而且异或的顺序是

可以交换的，交换并不会影响异或的最终结果，所以数组中所有元素异或之后，交换元素顺序，两

两相同的结合进行异或，通过异或运算我们会知道每两个相同的数字异或之后的结果为0，而多组0

之间异或后最后还剩一个0，然后就剩下那个只出现一次的数字和0之间进行异或，而由前面我们知

道任何数字和0异或结果为该数字，自此我们得到了所求结果，整个过程只需要一次循环去求数组

中所有元素之间的异或即可，优雅不优雅，美妙不美妙。

        以上仅为证明这个方法可以得到最终结果，计算机会按照先后顺序依次进行异或。

        下面是也是个关于异或的题目，有余力的可以尝试用异或做做看，很有意思的。第260题 只出现一次的数字Ⅲhttps://leetcode.cn/problems/single-number-iii/

2. 两个数字交换

        通常，我们引用一个变量去交换，但这会浪费一个空间。而如果通过异或的话就不需要占用

一个空间。

        int a = 30;
        int b = 23;
        if (a > b) {
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
        }

3. 两个数字判等

        我们已经知道当两个数字相等时，异或结果为0；因此我们可以利用这个特性去判等，效率更

高哦！

        

    a^b==0//与a==b一个意思

4. 加密

        在这里我们要拓展一下下面这个运算法则

        ①d = a ⊕ b ⊕ c   可以推出   ②a  =  d  ⊕  b  ⊕  c.  

        我们已经知道由 ① 可以推出 ② ，其实还可以推出 a  ⊕  b = c  ⊕  d

        此外，由 ① 推出 ② 我们可以知道 当我们得到其中的任意三个都可以推出另外一个

        同理，在 c = a ⊕ b 中我们也可以由其中的任意两个来推出另外一个

        这就引出了我们这里的内容，加密信息。

        在密文a 、密匙b 、明文c三者之间我们也可以利用异或来实现信息的加密。

        发送方可以通过密文异或密匙,来得到一篇明文发送给接收方，即 a ^ b = c 。

        而接收方则可以通过密匙和明文异或获得密文，即 b ^ c = a

        由此，我们就实现了信息的加密。

5. 备份

        同样的，利用上面推出的结论，我们也可以备份文件，那么怎么备份呢？让我们好好想想，

上面说到当我们得到三者中的任意两者就可以得到另外一个。那么我们是不是也可以设计一种类似

与密匙的东西，通过他的处理，我们将需要备份的文件与密匙异或得到一个恢复包。这样在原始文

件丢失的情况下，我们就可以通过密匙与恢复包异或得到丢失的文件。

 

 

 

 

五.最后的话

        第一次写博客，个别地方还不够完善，也参考了部分别人写的博客里的内容，如有什么错误

的地方，希望大家可以批评指正，也希望大家可以补充更多相关的内容，让我们共同进步，一起加

油吧！

 

 

 

 

 

 

 

 

 

参考如下：

https://blog.csdn.net/qq_19272431/article/details/78564391

https://blog.csdn.net/cuixianlong/article/details/90064348

https://zhuanlan.zhihu.com/p/453673815