Java-异或运算详解

左手的ㄟ右手 2023-10-08 20:53 41阅读 0赞

### 基本概念 ###

异或运算,符号为XOR或者^,是二进制的运算,运算法则为相同为0,不同为1,我记得时候反正总会忘(和同或记反),所以这里直接把异或理解为"**不进位的二进制相加**".举个栗子:

1000111 和 1110001 异或

按照不进位相加的运算方法:最小位都是1 相加为2也就是10(二进制运算), 因为是不进位的运算 所以直接本位为0 就可以了,其他位如法炮制:0110110.

### 重要性质 ###

异或运算符合交换律和结合律

交换律:a^b^c^d 和 a^d^c^b是一样的

结合律:a^b^c^d和a^(b^c)^d是一样的

0^N==N

N^N==0

### 应用场景 ###

#### 1.利用异或交换两个数 ####

绝大多数这个操作都是没屁硌楞嗓子的无意义操作....它的好处就是不用申请额外空间完成操作,但是不用异或操作也可以实现不申请额外空间的交换(异或操作还有可能出错)---[不创建临时变量交换两个变量传送门][Link 1](可以看下这篇博客)

int a = 10;
    int b = 11;
    a = a^b;
    b = a^b;
    a = a^b;
    System.out.println(a);
    System.out.println(b);

这三个a^b你懵不懵?反正我第一次看见是挺懵的

设 a的初始值为x b的初始值为y

a = x^y

b = (x^y)^y 因为y^y为0 x^0为x 所以b中现在存储的数据为 x(交换完成)

a = x^y^x 同理 ==x

(寄!写着写着发现按值传递按址传递好不悬给忘了)

值得一提的是因为异或操作的性质,如果a和b是同一块内存的话 会导致最后交换结果为0

#### 2.一个数组中有一个数出现了奇数次,其他数都出现了偶数次,找到并打印这个数 ####

这题用性质做爽的一匹,直接把他们全都异或在一起就行了,根据结合律,出现偶数个的数全都异或在一起变成零,而奇数个数的数异或在一起会剩下一个,然后本身和0异或还是本身;

public static int select(int arr[]) {
            int sum = 0;
            for(int i = 0;i<arr.length;i++) {
                sum^=arr[i];
            }
            return sum;
        }
    
        public static void main(String[] args) {
    
            int [] arr = {1,1,1,1,3,3,3,3,3,5,5,5,5};
            int a = select(arr);
            System.out.println(a);
    }

#### 3.取一个二进制数中的最后一个1 ####

如1001110 取得就是倒数第二个

我们先设N是一个二进制数

N: 1 0 0 0 1 1 1 1 1 1 1

~N: 0 1 1 1 0 0 0 0 0 0 0(取反)

~N+1:0 1 1 1 0 0 0 0 0 0 1

然后把N和~N+1进行按位与(&)操作

得到 0 0 0 0 0 0 0 0 0 0 1

public static int selectlastone(int n) {
            int n1 = ~n+1;
            int s = n&n1;
            return s;
        }
    
        public static void main(String[] args) {
    
            int n = 10;
            System.out.println(Integer.toBinaryString(n));//按二进制打印n
            int a = selectlastone(n);
            System.out.println(Integer.toBinaryString(a));//按二进制打印a
    }

#### 4.一个数组中有两个数出现了奇数次,其他数都出现了偶数次,找到并打印这个数 ####

public static int select(int[] arr) {
                int eor = 0;
                for (int i = 0; i < arr.length; i++) {
                    eor ^= arr[i];
                }
    
                int rightOne = (~eor+1)&eor; // 提取出最右的1
                
                
                int onlyOne = 0; 
                for (int i = 0 ; i < arr.length;i++) {
    
                    if ((arr[i] & rightOne) != 0) {
                        onlyOne ^= arr[i];
                    }
                }
                System.out.println(onlyOne);//onlyOne是其中一个
                return eor ^ onlyOne;//返回的是另一个
        }
    
        public static void main(String[] args) {
    
            int [] arr= {1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,4};
            int a = select(arr);
            System.out.println(a);
    }

设这两个单独的数分别为a b

先把所有数字都异或在一起 偶数消除掉 留下的是 a^b

a和b至少有一位是不同的 所以a^b里面至少有一个1 我们取出左右边的1 得到rightone

a或者b不同的话 这个位置上肯定其中一个是 1 一个是 0;

我们假设a这个位置上是1 b这个位置上是0

(反正除了我们要找的数以外都是偶数个,剩下的那些本位置为1的数是0个还是6个8个都不重要)

可以把这个数组分为两组 A组 这个位上为1的元素 B组 这个位上为0的元素

而在A组中 包含偶数个其他元素和奇数个a 所以再次转变成问题2求出onlyone

然后再有a^b = eor a^eor = b 求出另一个元素

#### 5.求二进制数中有多少个1 ####

public static int onecount(int a) {
                int count = 0;
                while(a!=0) {
                    int rightone = ((~a)+1)&a;
                    count++;
                    a ^= rightone;
                }
                return count;
        }
    
        public static void main(String[] args) {
    
            int a = 55;
            int count = onecount(a);
            System.out.println(count);
    }

用应用3轻松解决

[Link 1]: https://mp.csdn.net/mp_blog/creation/editor/125714323