异或运算符 ^

一颗蔬菜 2018-11-22 PM 70℃ 0条
运算方法

无进位运算

异或运算的性质

交换律:a ^ b = b ^ a
结合律:a ^ b ^ c = a ^ (b ^ c)
N ^ 0 =N
N ^ N =0

代码实现

int a = 1,b = 2 ; , 交换a和b的值。

// 常规操作
int temp = a;
a = b;
b = temp;

// 异或运算
a = a ^ b; // a = a ^ b ,b = 2 
b = a ^ b; // b = a ^ b ^ b = a ,a = a ^ b ,b = 1
a = a ^ b; // a = a ^ b ^ a = b ,a = 2

异或运算要求符号两边的数不在同一个内存区域,看下面的代码

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
// 按照异或运算的规则,i和j是不能相等的,进行异或运算的两个数的内存地址不能相同
// 但它的值是可以相同的

注意,在写算法的题的时候尽量用第二种方式写,因为很多情况下,会出现比较同一个内存地址的值的情况。

经典算法题

(1) 一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到这一个数

(2) 一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到这两个数

答:(1)定义一个变量eor,遍历整个数组,将eor和数组中的每个数都进行异或运算,偶数次的数在异或运算中都会被抵消,而没有被抵消的就是那个出现了奇数次的数。(2) 根据对第一问的理解,若存在两个出现奇数次的数,则最后遍历整个数组进行异或运算的结果是a ^ b。而a和b不相等,假设a、b是位数为n的二进制数,a和b的某一位一定不同,如a = 1111、b = 1101,a、b的第三位分别为1、0,因此用0010分别和a、b做位运算,求出a、b中的一个赋值给oneOddTimesNum,然后再用oneOddTimesNum与eor做异或运算就能求出另一个。

代码实现:

public void printOddTimesNum(int[] arr) {
        // eor: a ^ b, oneOfOddTimesNum = a or b
        int eor = 0,oneOfOddTimesNum = 0;
        for (int currentNum : arr) {
            // 遍历整个数组,做异位运算
            eor ^= currentNum; // eor = a ^ b
        }
        int rightOne = (~eor + 1) & eor;  
        // 求出a、b从右至左第一个不相同的位置,将该位置赋值为1其他位置赋值为0
        // eg: a = 0111 ,b = 1001 ,rightOne = 0010;
        //     a = 1000 ,b = 1100 ,rightOne = 0100;
        for (int currentNum : arr) {
            if ( (rightOne & currentNum) != 0) {
                oneOfOddTimesNum ^= currentNum;
                break;
            }
        }
        System.out.print("a = " + oneOfOddTimesNum+", b = " + (oneOfOddTimesNum ^ eor));
    }
基础知识

~ 是取反运算符,~ 1000 = 0111 , ~ 010 = 101

& 是按位与运算符,10010 & 10000 = 10000 , 1100 & 1101 = 1100

标签: 算法

非特殊说明,本博所有文章均为博主原创。

上一篇 没有了
下一篇 DI控制反转和IOC依赖注入