异或位算法的高效玩法

陈皮的JavaLib

关注

发布于: 1 小时前

我是陈皮，一个在互联网 Coding 的 ITer，微信搜索「陈皮的 JavaLib」第一时间阅读最新文章，回复【资料】，即可获得我精心整理的技术资料，电子书籍，一线大厂面试资料和优秀简历模板。

1 异或位运算

异或，符号为 ^，关于异或位运算的规则如下，即相反得 1 ，相同得 0 。

1 ^ 0 = 1
1 ^ 1 = 0
0 ^ 0 = 0
0 ^ 1 = 1
0 ^ N = N
N ^ N = 0
A ^ B = B ^ A（交换律）
A ^ B ^ C = A ^ (B ^ C)（结合律）

2 高效玩法

2.1 两个数值交换

题目：如何快速实现 2 个整数变量值的交换，我们可以会借助第三个临时变量来实现：

正常情况下，我们会借助第三个临时变量来实现。

private static void swap(int[] arr, int i, int j) {    // 借助temp变量    int temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}

复制代码

比较高效的是通过异或位运算来实现，不用借助第三个临时变量。

private static void swap(int[] arr, int i, int j) {    arr[i] = arr[i] ^ arr[j];    arr[j] = arr[i] ^ arr[j];    arr[i] = arr[i] ^ arr[j];}

复制代码

为何经过 3 次异或运算就实现了 2 个数值的交换了呢？下面进行分析论证：

a  = a ^ bb =  a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a // 此时变量b的值就变成a了a = a ^ b = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b // 此时变量a的值就变成b了

复制代码

那在使用异或位运算交换 2 个变量的值时，需要注意什么呢？需要注意的是如果交换的两个变量的值一样的话，会导致最终两个变量的值都变为 0，出现错误。

a  = a ^ b = a ^ a = 0b =  a ^ b = 0 ^ 0  = 0a = a ^ b = 0 ^ 0  = 0

复制代码

所以用异或位运算实现 2 个变量数值的交换的前提条件是它们的数值不能相等。

2.2 数组找奇数

题目：一个数组中，有一种数字出现了奇数次，其他数字都出现了偶数次，如何快速找到这个奇数次的数字呢？

根据 2 个相同的数进行异或的结果为 0，那么偶次数的相同数字进行异或最终的值也为 0，最后 0 与那一个多出来的奇数次的数进行异或，最终的值即为这个出现了奇数次的数字。

package com.chenpi;
import java.util.Arrays;
/** * @Description * @Author 陈皮 * @Date 2021/08/05 * @Version 1.0 */public class ChenPiMain {    public static void main(String[] args) {        // 只有4是出现了奇数次        int[] arr = {1, 2, 6, 4, 1, 2, 1, 1, 4, 4, 6};        int eor = 0;        for (int e : arr) {            // 将所有数进行异或            eor ^= e;        }        System.out.println(eor); // 输出结果为4    }}

复制代码

2.3 提取二进制最右侧 1

题目：对于一个整数的二进制形式，如何提取最右侧的 1？例如整数 20，二进制是 00010100 ，提取最右侧的 1，即为 00000100 。

思路很清楚，最右侧的 1 它的右边肯定都是 0，那就保证 1 位置左侧的所有位的值都变为 0 即可。

要让左边的位都变为 0，根据与操作的特性，1&0=0，那就让左边的所有位取反相与即可。
右边的位都为 0，取反后都变为 1，再加 1 因为进位所以都会重新变成 0。
因为最右侧的 1 取反后，变为 0，然后右侧加 1 又进位，最后恢复为 1。
所以采用算法：N & (~N + 1)

     N = 00010100    ~N = 11101011~N + 1 = 11101100
N & (~N + 1) : 00010100             & 11101100             = 00000100

复制代码

Java 语言实现如下：

package com.chenpi;
/** * @Description * @Author 陈皮 * @Date 2021/08/05 * @Version 1.0 */public class ChenPiMain {    public static void main(String[] args) {        int N = 20;        System.out.println(Integer.toBinaryString(N));        int result = N & (~N + 1);        System.out.println(Integer.toBinaryString(result));    }}
// 输出结果10100100

复制代码

2.4 数组找双奇数

题目：一个数组中，有两种数字出现了奇数次，其他数字都出现了偶数次，如何快速找到这个两个奇数次的数字？

思路：

假设这俩个数分别为 a 和 b ，因为 2 个相同的数异或等于 0，则将数组所有数进行异或操作后，结果 result = a ^ b。
因为这两个数的值不同，所以 result=a ^ b != 0，即 result 二进制形式肯定存在 1 的位，而这个 1 又是 a 和 b 异或出来的。那 a 和 b 的二进制位对应位置上，它们分别为 0 和 1，才能异或出 1 。
我们就取最右侧位置（假设 Li ）的 1 来说，那数组中所有数，它们的 Li 位置要么就是 1，要么就是 0。而且 a 和 b 的 Li 位置是不一样的（不妨假设 a 的 Li 位置是 1，b 的 Li 位置是 0）。
所以我们可以将数组中的所有数划分为 2 组，Li 位置是 1 的一组，Li 位置是 0 的一组。相同的数肯定在同一组，即其他偶次数的数在同一组（可以两两异或值为 0），所以分别将组内的所有数进行异或，即可找出那 2 个奇数。

package com.chenpi;
/** * @Description * @Author 陈皮 * @Date 2021/08/05 * @Version 1.0 */public class ChenPiMain {    public static void main(String[] args) {        // 只有4和11是出现了奇数次的数组        int[] arr = {1, 2, 6, 4, 1, 2, 1, 1, 4, 4, 6, 11};
        // 首先将数组所有数进行异或，结果result = a ^ b;        int result = 0;        for (int e : arr) {            result ^= e;        }
        // 提取最右侧的1        int rightOne = result & (~result + 1);
        // 将其中一组（Li位置是1）的数进行异或，        int eor1 = 0;        for (int e : arr) {            if ((e & rightOne) != 0) {                eor1 ^= e;            }        }        System.out.println("这两个数分别为：" + eor1 + " " + (eor1 ^ result));    }}
// 输出结果这两个数分别为：11 4

复制代码

2.5 计算二进制的 1 的个数

题目：如何计算一个整数的二进制形式中，1 的个数？

只需要从最右侧的 1 开始往左数，数一个之后，将这个 1 置为 0，再继续数。
其实就是每次都提取出最右侧的 1，计算+1，然后将这个 1 置为 0，再继续提取 1，计数....

package com.chenpi;
/** * @Description * @Author 陈皮 * @Date 2021/08/05 * @Version 1.0 */public class ChenPiMain {    public static void main(String[] args) {        int num = 45;        System.out.println("二进制：" + Integer.toBinaryString(num));        int count = 0;        while (num != 0) {            int rightOne = num & (~num + 1);            count++;            num ^= rightOne;        }        System.out.println("1的个数：" + count);    }}
// 输出结果二进制：1011011的个数：4

复制代码

本次分享到此结束啦~~

如果觉得文章对你有帮助，点赞、收藏、关注、评论，您的支持就是我创作最大的动力！

发布于: 1 小时前阅读数: 6

原文链接:【http://xie.infoq.cn/article/9efcfe2d29c2e2e9692552706】。未经作者许可，禁止转载。

陈皮的JavaLib

关注

CSDN博客专家，微信搜一搜 - 陈皮的JavaLib 2020.02.22 加入

CSDN博客专家，专注各项技术领域的Java开发工程师，微信搜一搜【陈皮的JavaLib】，关注后学习更多技术文章和一线大厂面试资料和技术电子书籍。

发布

暂无评论

创作场景

异或位算法的高效玩法

1 异或位运算

2 高效玩法

2.1 两个数值交换

2.2 数组找奇数

2.3 提取二进制最右侧 1

2.4 数组找双奇数

2.5 计算二进制的 1 的个数

陈皮的JavaLib

评论