位运算之异或(XOR)

原创

CoffeeLand

修改于 2020-03-30 11:07:18

1.6K0

修改于 2020-03-30 11:07:18

文章被收录于专栏：CoffeeLandCoffeeLand

XOR是什么

是计算机的逻辑异或运算

XOR的运算规则

相同为0, 不同为1

 1000 ^ 1001 的运算过程如下
 1001
 1000
=0001

XOR的应用

判断两个数是否相等

通过判断两个数异或结果是否为0来判断两个数是否相等

int a=10,b=20,c=10;
a^b 不是0, 所以不相等
a^c 是0， 所以相等

不用第三个变量来交换两个数

        int a = 10;
        int b = 20;

        a = a^b;
        System.out.println("a = " + a);
        b = a^b;
        System.out.println("b = " + b);//10
        a = a^b;
        System.out.println("a = " + a);//20

        a = a ^ a;
        System.out.println("a = " + a); //0

返回一个数的二进制形式的最右边的一个1

1010 最右侧1是0010

1100 最有测1是0100

二进制减法的一个特性

一个二进制数减1, 相当于把这个数的从最右侧的1开始flio翻转

1000 – 0001 = 0111

0100 – 0001 = 0011

1100 – 0001 = 1011

然后使用如下算法

x ^ (x & (x - 1))
// x-1 是为了找出最右侧1的位置, 
// x & (x - 1) 是将从右侧的位置开始的位置为0
// ^ 是根据相同为0, 不同为1, 最右侧之前的位置为0

HashMap的hash算法

 // java8的hashMap的hash
   static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //h >>> 16 是为了将高位移向地位
    //异或运算 是因为index = (n-1) & hash; n是数组的长度, 为了防止hash散列冲突
    //java7的是hash % n, java8用无符号右移是因为位运算快