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

1 异或位运算

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

  1. 1 ^ 0 = 1

  2. 1 ^ 1 = 0

  3. 0 ^ 0 = 0

  4. 0 ^ 1 = 1

  5. 0 ^ N = N

  6. N ^ N = 0

  7. A ^ B = B ^ A(交换律)

  8. 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 ^ b
b =  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 = 0
b =  a ^ b = 0 ^ 0  = 0
a = 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 即可。

  1. 要让左边的位都变为 0,根据与操作的特性,1&0=0,那就让左边的所有位取反相与即可。

  2. 右边的位都为 0,取反后都变为 1,再加 1 因为进位所以都会重新变成 0。

  3. 因为最右侧的 1 取反后,变为 0,然后右侧加 1 又进位,最后恢复为 1。

  4. 所以采用算法: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));
    }
}


// 输出结果
10100
100

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


// 输出结果
二进制:101101
1的个数:4


本次分享到此结束啦~~

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

本文文字及图片出自 InfoQ

余下全文(1/3)
分享这篇文章:

请关注我们:

发表评论

邮箱地址不会被公开。 必填项已用*标注