数据结构（Java）--位运算

前言

本文为本小白学习数据结构的笔记，将以算法题为导向，向大家更清晰的介绍数据结构相关知识（算法题都出自B站马士兵教育——左老师的课程，讲的很好，对于想入门刷题的人很有帮助）

为什么要使用为位运算

位运算直接对整数的二进制位进行操作，因为在计算机中数据都是以二进制存储的，因此它在许多场景下能够提供比传统算术和逻辑运算更高效、更简洁的解决方案。

常见的几种位运算

1.位与&

十进制转二进制 两个都为1则为1，否则为0

例：判断奇偶数：x&1=1（x为奇数 ） x&1=0（x为偶数）

2.位或|

十进制转二进制 两个都为0则为0，否则为1

3.异或^

十进制转二进制 两个数都相同为0，否则为1

(满足交换律，相同的数异或位0，任何数和0异或都等于这个数本身）

4.按位取反~

变为二进制后，0变1，1变0，高位不足取0

5.左移 x<<y

变为二进制后，x左移y位，补零。相当于乘二。

6.右移 x>>y

变为二进制后，x右移y位，x为非负数高位补零，为负数高位补1。

例：（x+y）>>1右移一位相当于除以二

下面列几个比较好玩的运算的例子：

1. 实现a与b值的交换

//实现a与b值的交换

    a = a ^ b;
    b = a ^ b;    //  b=a^b^b=a
    a = a ^ b;    //  a=a^b^b

2. 想查x第n位是否为1：x&（1<<n)

3.把x的第n位设置为1/0；

为1

为0

4.取出x最右位的1

eor=eor & (~eor + 1)

5.在一个int arr[] 数组中，一种数出现了奇数次，其余树出现偶数次

（1）找到出现奇数次的数
（2）如果两种数出现奇数次，其他偶数次，怎样找到这两种数
要求时间复杂度O(n),空间O(1)

//第一问
//所有数全部异或运算得出
public static void Num1(int[] arr){
    int eor = 0;
    for (int cur : arr) {
        eorr ^= cur;
    }
    System.out.println(eor);
}

//第二问
//假设两个出现奇数次的数为a和b，将所有数全部异或得出eor=a^b
public static void Num2(int[] arr){
    int eor = 0;
    for (int cur : arr) {
        eorr ^= cur;
    }
    //eor 必有一位上是1
    int rightOne = eor & (~eor + 1);//取出最右位的1
    
    int onlyOne = 0;
    for(int aur : arr){
       if((aur & rightOne) == 0) {
           onlyOne ^= aur;
       }
    }
    System.out.println(onlyOne + " " +(eor^onlyOne));
}