位运算中异或的常见用法总结

灰太狼 2021-12-17 09:11 367阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

异或(^) 这个位操作运算符相信大家一定都不陌生，这个运算符可以用来解决很多普通算法解决不了的问题，而且位运算是直接对二进制码做运算，相对普通的加减乘除运算符来说的话更加的高效，我们借着题目一起来看看。

对两个输入参数做加法运算，但是不能使用 “+” 运算符 。

### 解法思路 ###

看到这样的问题，能想到的只有位运算，问题是怎么算？相信大家小学刚学习加法的时候，对于一下子不能得到答案的题，肯定会在草稿纸上列竖式，从右向左算，同一列对下来的数字相加如果超过 10，那么肯定要在下面写两个数字相加后的个位数，然后往前进一位，下一位运算时就要加上这个进位，用这样的方式直到最后算出结果。这题的思路也是一样的，只不过有两点不一样，第一，10 进制变成了 2 进制，第二，我们不再是在草稿纸上列竖式，而是要写成计算机看得懂的代码，这就得借助我们的位运算了，因为 2 进制表示的数中只会出现 0 和 1，你可以把这两个数看成是 true 和 false，这样更好理解，我们可以先通过异或塞选出不用进位的情况，然后再用与运算和左移运算计算出进位的情况，迭代更新出最后的结果。

### 参考代码 ###

public int plus(int a, int b) {    int aTemp = 0, bTemp = 0;    while (b != 0) {        aTemp = a ^ b;        bTemp = (a & b) << 1;        a = aTemp;        b = bTemp;    }    return a;}
        int aTemp = 0, bTemp = 0;
        while (b != 0) {
        
            aTemp = a ^ b;
            bTemp = (a & b) << 1;
            a = aTemp;
            b = bTemp;
        }
    
        return a;
    }

如何在不创建临时变量的情况下进行交换两个数？

### 解法思路 ###

异或的常见应用，很简单，但是注意思考角度从位出发，而不是数，这点很重要。

### 参考代码 ###

public void swap(int a, int b) {    a ^= b; // a 中存放两数互异的点位    b ^= a; // 取反 b 中不同于 a 的点位，也就是实现了 b = a    a ^= b; // 取反 a 中不同于 b 的点位，也就是实现了 a = b}
        a ^= b; // a 中存放两数互异的点位
        b ^= a; // 取反 b 中不同于 a 的点位，也就是实现了 b = a
        a ^= b; // 取反 a 中不同于 b 的点位，也就是实现了 a = b
    }

如果把 A 转换成 B ，需要改变多少位？

### 解法思路 ###

异或的简单应用，两个数做异或的结果就是两个数差异所在，然后只需计算这个结果中有多少个 1 即可。

### 参考代码 ###

public int convertA2B(int A, int B) {    int n = A ^ B;    int count = 0;    while (n != 0) {        n = n & (n - 1); // n - 1 是将 n 的最低位为零        count++;    }    return count;}
        int n = A ^ B;
        int count = 0;
        while (n != 0) {
        
            n = n & (n - 1); // n - 1 是将 n 的最低位为零
            count++;
        }
    
        return count;
    }

LeetCode 第 136 号问题：给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

### 解法思路 ###

异或的三个点顺下来，就可以很清楚地解这道题：

异或运算和乘法一样，位置和运算顺序不影响最后结果：`a^b^c = b^c^a`  
两个相同的数做异或运算结果为零：`a^a = 0`  
任何数和零做异或结果还是这个数本身：`a^0 = a`

### 参考代码 ###

public int findOnce(int[] arr) {    int result = 0;    for (int i = 0; i < arr.length; ++i) {        result ^= arr[i];    }    return result;}
        int result = 0;
        for (int i = 0; i < arr.length; ++i) {
        
            result ^= arr[i];
        }
    
        return result;
    }

LeetCode 第 137 号问题：给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

### 解法思路 ###

这题的难点在于 3 次，如果把数组里面的数字就当作数字本身来看的话，很难找到突破口；如果想到了位运算，那就要有一个概念就是位运算是基于位的，而不是基于数的，在这个问题中，所有的 bit 的出现次数只会有两种情况，`3*n，3*n + 1`,这里的 n 是任意整数，假设你遍历数组，其实会有一个中间态就是 `3*n + 2` 存在，对于除这个数以外的其他数，过程大概是 `3*n + 1` \-> `3*n + 2` \-> `3*n`，我们只要记录的就是 `3*n + 1` 和 `3*n + 2`的情况，因为 `3*n` 其实就是一个初始状态（n=0）,记不记录和我们最后要返回的答案无关，而记录 `3*n + 2` 是为了恢复一些 bit 从 `3*n + 2` 到 `3*n`

### 参考代码 ###

public int singleNumber(int[] nums) {    int ones = 0, twos = 0;    for (int i = 0; i < nums.length; ++i) {        // 找出当前的 3n + 1        ones = (nums[i] ^ ones) & (~twos);        // 找出当前的 3n + 2        twos = (nums[i] ^ twos) & (~ones);    }    return ones;}
        int ones = 0, twos = 0;
        for (int i = 0; i < nums.length; ++i) {
        
            // 找出当前的 3n + 1
            ones = (nums[i] ^ ones) & (~twos);
            // 找出当前的 3n + 2
            twos = (nums[i] ^ twos) & (~ones);
        }
    
        return ones;
    }

LeetCode 第 260 号问题：给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

### 解法思路 ###

这题的主要难点是如何把两个数给拆出来，如果直接运用异或算法，我们最后得到的结果是两个数做异或的结果，关键点是如何基于这个异或的结果来找到这两个数，有一点很重要的就是，异或的结果为 1 的点位只会出现在其中一个数中，我们可以用其中一个为 1 的点位作为判断依据，这个点位存在的所有数在一起做异或，这个点位不存在的所有数一起做异或，这样就把这个问题拆解成了两个 problem 3。

### 参考代码 ###

public int[] singleNumber(int[] nums) {    if (nums == null || nums.length == 0) {        return new int[2];    }    int different = 0;    for (int i : nums) {        different ^= i;    }    different &= -different;    int[] ans = {0, 0};    for (int i : nums) {        if ((different & i) == 0) {            ans[0] ^= i;        } else {            ans[1] ^= i;        }    }    return ans;}int[] singleNumber(int[] nums) {
        
        if (nums == null || nums.length == 0) {
        
            return new int[2];
        }
    
        int different = 0;
        for (int i : nums) {
        
            different ^= i;
        }
    
        different &= -different;
        int[] ans = {
        0, 0};
        for (int i : nums) {
        
            if ((different & i) == 0) {
        
                ans[0] ^= i;
            } else {
        
                ans[1] ^= i;
            }
        }
    
        return ans;
    }

总结

位运算相对其他的运算来说更加的高效，异或在位运算中的应用非常广，但是这里的难点是我们平时可能会忽视位运算，导致我们遇到一般的问题不会往位运算的方向去想，另外就是如果对二进制的运算不熟，我们也很难理解一些位运算的综合操作，这里提到了异或可以交换两个数，做加法操作，还可以用来解决一些问题。

欢迎你来分享你对异或以及位运算的认识。

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 1] 你点的每个“在看”，我都认真当成了喜欢

[640_wx_fmt_jpeg]: /images/20211217/d3719d07db4b4b77a6feae8d8cb21955.png
[640_wx_fmt_png]: /images/20211217/54def50fe74a454baa777bb13583aa9e.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 1]: /images/20211217/fe540c3bdc6a44ab8311ad8f33f128cb.png