• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

异或运算

开发技术 开发技术 4小时前 4次浏览

异或运算

异或运算实现数值交换

package dataStructuresAndAlgorithms;

public class BitOperation {
    public static void main(String[] args){
        int a = 2;
        int b = 3;

        a = a^b;  // a = 2^3 b = 3;
        b = a^b;  // a = 2^3 b = 2^3^3 = 2
        a = a^b;  // a = 2^3^2 = 3 b = 2
        System.out.println("a = "+a+ " b = "+b);
    }
}

其中:

​ 1、0 与任何数异或,得到数的本身,任何数和自身进行异或,得到0;

​ 2、数学的交换律和结合律适用于异或运算,即:a^b = b^a; a ^ b ^ c = a ^ ( b ^ c);

​ 3、这种交换方式的实现前提是,变量所指的地址必须不同,值可以相同;

注:异或运算可理解为不进为的二位运算,即:1+1 =0; 1+0 = 1;

异或面试题

1、数组中,有一种数出现的次数是奇数次,其余的都是偶数次,查找出这个数;

2、数组中,有俩种数出现的次数是奇数次,其余的都是偶数次,查找出这俩个数;

解:

1:

public static void getOddNumber(){
        int[] arr = {2,3,2,2,3,3,2,6,6,7,6,7,6};
        int eor = 0;
        for(int number:arr){
            eor = eor^number;
        }
        System.out.println(eor);
    }

运行结果:3

分析:异或运算满足交换律和结合律,与元素的异或顺序无关,将数组种,相同的元素交换到一起,即可获得:

{2,2,2,2,3,3,6,6,6,6,7,7}

出现次数为偶数的数字,经过异或运算,会成为0,剩余的元素即为出现次数为奇数的元素。

2:

//获取出现次数为奇数的俩个元素 a,b
    public static void getTwoOddNumber(){
        int[] arr = {3,3,4,6,6,8,7,7,7,8,8,8};
        int eor  = 0;
        /*
         * 异或运算完,此时:eor = a^b = 4^7
         * 即:eor != 0,
         * 可得: eor的二进制上,必有一个位置不为0
         * */
        for(int number:arr){
            eor = eor^number;
        }

        /*
         * ~eor: 为取反操作,列:eor = 100000011 则~eor = 011111100
         * ~eor+1: 例:~eor = 011111100 ,则: ~eor+1 = 01111101
         * eor & (~eor+1):与运算 例: eor & (~eor+1) = 11111111(同为1则为1.否则为0)
         * 此写法能够找出右边第一出现1的数
         * 现在已经找出 eor = a^b 上为1的位置
         * */
        int rightOne = eor & (~eor + 1);
        /*
        * 已经得出eor不为0的位置,进行与运算时,会自动将出现次数为偶数的元素消掉
        * 当数组元素与rightOne进行与运算时,出现为0或者1的数,即为a或者b
        * */
        int onlyOne = 0;
        for(int number : arr){
            if((number & rightOne) == 0){
                onlyOne ^= number;
            }
        }
        /*
        * 将已经得到的出现次数为奇数的一个数,与eor进行异或运算,即可得到另一个数
        * */
        int otherOnlyOne = eor^onlyOne;
        System.out.println("一个数为:"+onlyOne+" 另一个是:"+otherOnlyOne);
    }

运行结果:一个数为:4 另一个是:7


程序员灯塔
转载请注明原文链接:异或运算
喜欢 (0)