异或运算实现数值交换

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

异或运算