当前位置：首页 > news >正文

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

news 来源：原创 2024/7/1 5:06:04

文章目录

1. 变量值交换方法1
2. 变量值交换方法2
3. 理解异或位运算，相当于无进位相加
4. 数组中只有一种数出现了奇数次，找出这种数
5. 数组中只有两种数出现了奇数次，找出这两种数
6. 把不等于0的数最右侧的的1提取出来，其余数置为0，得到值形如：0000100

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;}// 由于只有a、b是奇数次：eor = a ^ b;// 由于是两种数，所以它们不相等：eor != 0;// 由于不等于0：eor必然有一个位置上是1int rightOne = eor & (~eor + 1); // 把不等于0的数最右侧的的1提取出来，其余数置为0，得到值形如：0000100for (int cur : arr) {// 等于1亦可，两个奇数次的数在rightone等于1这个这个位置异或为1，代表它们在这个位置一个为0，一个为1// 偶数次的数也会被分为两个阵营，不过下面onlyOne与其中一个阵营异或，由于不管哪个阵营都是偶数次，阵营内部异或结果都是0
//            if ((cur & rightOne) == 1) { if ((cur & rightOne) == 0) {// 将onlyOne，初始为0，与两个奇数次的数中的一个，设为a，和偶数次数的一个阵营异或得到的就是a，// 因为其他的数都是偶数次，一起异或得到0，那么只剩下所有的a异或，由于是奇数次，所以结果是aonlyOne ^= cur;}}// 所以onlyOne就是a，eor = a ^ b; b = eor ^ a;System.out.println(onlyOne + "\n" + (eor ^ onlyOne));}