数据结构与算法2-俩变量值交换、理解异或位运算

文章目录

1. 变量值交换方法1
2. 变量值交换方法2
3. 理解异或位运算，相当于无进位相加
4. 数组中只有一种数出现了奇数次，找出这种数
5. 数组中只有两种数出现了奇数次，找出这两种数

1. 变量值交换方法1

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

2. 变量值交换方法2

    public static void swap(int[] arr, int i, int j) {
        // 这里的i 和 j 不能相等，否则就用到了同一内存，就会变为0；
        // arr[i] 和 arr[j]的值可以相等，它们的值是存在不同栈中，并不是同一块内存
        if (i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

步骤分析：

int a = 甲;
int b = 乙;
a = a ^ b; // a = 甲 ^ 乙;
b = a ^ b; // b = 甲 ^ 乙 ^ 乙 = 甲 ^ (乙 ^ 乙) = 甲 ^ 0 = 甲
a = a ^ b; // a = 甲 ^ 乙 ^ 甲 = 甲 ^ 甲 ^ 乙 = 0 ^ 乙 = 乙

3. 理解异或位运算，相当于无进位相加

异或位运算原理：相同为0，不同为1

0 1 -> 1
1 0 -> 1
0 0 -> 0
1 1 -> 0

满足的性质：

0 ^ N = N
N ^ N = 0;
满足交换律：a ^ b = b ^ a;
满足结合率：a ^ b ^ c = a ^ (b ^ c);

4. 数组中只有一种数出现了奇数次，找出这种数

	public static void main(String[] args) {
        int[] arr = {2, 2, 3, 3, 7};
        printOddTimesNum1(arr);
    }


    /*
     * 数组中只有一种数出现了奇数次，找出这种数
     *
     * */
    public static void printOddTimesNum1(int[] arr) {
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        System.out.println(eor);
    }

打印结果：

7

5. 数组中只有两种数出现了奇数次，找出这两种数

	public static void main(String[] args) {
        int[] arr2 = {2, 2, 3, 3, 7, 8};
        printOddTimesNum2(arr2);
    }

    /*
     * 数组中只有两种数出现了奇数次，找出这两种数
     *
     * */
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0, onlyOne = 0;
        for (int curNum : arr) {
            eor ^= curNum;
        }
        // eor = a ^ b;
        // eor != 0;
        // eor必然有一个位置上是1
        int rightOne = eor & (~eor + 1); // 提取出最右的1
        for (int cur : arr) {
            if ((cur & rightOne) == 0) {
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + "\n" + (eor ^ onlyOne));
    }