02、算法与数据结构 - 实战：位运算
不使用额外变量，进行两个数的交换
异或运算：
1、 两个数做异或运算，等于两个数的二进制位做无进位相加；
2、 一个数自己跟自己异或，结果为0（N^N==0）；
3、 任何数跟0异或，结果为自己本身（N^0==N）；
/**
* 不使用额外变量，进行两个数的交换
*/
public class BitOperation01 {
public static void main(String[] args) {
int a = 2;
int b = 3;
a = a ^ b; // a = a ^ b
b = a ^ b; // b = a ^ b ^ b = a
a = a ^ b; // a = a ^ b ^ a = b
System.out.println(a);
System.out.println(b);
}
}
一个数组中，一种数出现了奇数次，其余数出现偶数次，找到并打印这种数
只要把所有的数异或在一起，得出的结果就是那个出现了奇数次的数。
因为一组数的异或得出的结果总是相同的，与这组数的排序无关。
而一个数和自己异或的结果为0，和0异或的结果是自己，所以所有数异或在一起，相当于相同的数两两异或，剩下一个出现奇数次的数。
/**
* 一个数组中，一种数出现了奇数次，其余数出现偶数次，找到并打印这种数
*/
public class BitOperation02 {
public static void main(String[] args) {
int[] arr = {
1,4,6,1,6,8,4,9,9};
int eor = arr[0];
for (int i = 1; i < arr.length; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
}
因为相同的数做异或运算，得出的结果是0，而任何数跟0做异或运算，得出的结果都是该数自身，所以遍历数组中所有的数，进行异或运算，最后得出的结果就是出现了奇数次的数。
怎么把一个整形最右侧的1提取出来？
一个数与上自己的取反加1，就能提取出最右侧的1：a & (~a + 1) = a & -a
一个数组中，两种数出现了奇数次，其余数出现偶数次，找到并打印这两种数
假设出现奇数次的数是 a ^ b
1、 先把所有的数异或起来，得到的结果是a^b；
2、 然后提取出最右侧的1；
3、 把这一位为1的数异或在一起，就可以得到其中一个出现奇数次的数；
4、 再把结果异或上a^b，则得到另一个出现奇数次的数；
原理： 因为a ^ b 的最右侧为1的位置，a和b在这一位上的值是不一样的（否则就不会异或后这一位为1），那么把所有的数分两组：这一位为1的和这一位不为1的，a和b比被分到不同组，而组中其他数又是出现偶数次的，异或起来后就是0，那么剩下的就是出现奇数次的数。
/**
* 一个数组中，两种数出现了奇数次，其余数出现偶数次，找到并打印这两种数
*/
public class BitOperation03 {
public static void main(String[] args) {
int[] arr = {
1,4,6,1,6,8,9,9}; //4和8出现奇数次，现在要找出4和8
int eor = arr[0];
for (int i = 1; i < arr.length; i++) {
eor ^= arr[i];
}
//此时eor为 4 ^ 8
//两个不等的数异或运算，得出的结果必然不等于0，取出eor最右侧的1
eor = eor & (~eor + 1);
//此时可以遍历数组，把数组分两组：1、和eor最右侧1相同二进制位上为1的；2、和eor最右侧1相同二进制位上为0的
//此时出现奇数次的两个数，必然落在不同组，分别对这两组数进行异或运算，得出两个出现奇数次的数
int a = 0;
int b = 0;
for (int i = 0; i < arr.length; i++) {
if ((arr[i] & eor) == 0) {
a ^= arr[i];
} else {
b ^= arr[i];
}
}
System.out.println(a);
System.out.println(b);
}
}
一个数组中，所有数都出现m此，只有一种数出现k次，找到并返回这种数
一个数组中，所有数都出现m此，只有一种数出现k次，找到并返回这种数
m>1，k < m
要求空间复杂度O(1)，时间复杂度O(n)
思路： 1、 声明一个32长度的整形数组bits（因为是固定长度的，所以空间复杂度还是O(1)）；
2、 将每一个数的每一位累加到数组bits对应位置上；
3、 然后数组每一个位数都模m，如果模完之后，该位上的数不为0，代表这个出现k次的数的对应的bit位为1；
/**
* 一个数组中，所有数都出现m此，只有一种数出现k次，找到并返回这种数
* m > 1，k < m
* 要求空间复杂度O(1)，时间复杂度O(n)
* Created by huangjunyi on 2022/11/19.
*/
public class BitOperation04 {
public static int findKTimes(int[] nums, int k, int m) {
// 一个32位的整形数组，存储每一个数的的每一个bit位相加
int[] bits = new int[32];
for (int num : nums) {
for (int i = 0; i < 32; i++) {
bits[i] += ((num >> i) & 1);
}
}
int res = 0;
for (int i = 0; i < bits.length; i++) {
// 如果一个bit位上，% m 后，不为0，代表这一位上，出现k次的数是1
if (bits[i] % m != 0) res |= (1 << i);
}
return res;
}
}