02-异或算法
2. 异或算法
2.1 异或基础
- 0^N == N N^N == 0；
- 记为无进位相加即可，1+1 = 0；
- 异或运算满足交换律和结合。
2.1.1 不用额外变量交换两个数
解法：aba = b，abb = a。
2.1.2 找出现奇数次的数
1. 题目
一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数。
2. 思路
数组里每个元素都异或，两两相消，就只剩下奇数次的那个数
3. 代码
public static void main(String[] args) {
int[] arr = {1,3,4,1,3,4,1,3,4,5,1,3,4};
int ans = 0;
for (int i = 0; i < arr.length; i++) {
ans ^= arr[i];
}
System.out.println(ans);
}
2.2 提取右侧(最低位)的1
1. 题目
怎么把一个int类型的数，提取出最右侧(最低位)的1来
2. 思路
1. 取反加一再和原来相与 a&(~a+1)
取反：这样每一位都不一样，之前的0位置都变成了1，假设此时的值为b。
加一：这样在右面+1就可以让他一直进位直到第一个0（也就是没取反的时候的1的位置），假设此时值为c。
相与：此时c的状态是最低的1往右的值都是0，最低一位的1的位置和a相同，这一位再往右每一个都是不一样的，所以相与之后，直接就可以得到结果。
注意: ~a+1 就等于-a，所以也可以写成a&(-a)
2. 直接暴力
先找位置，然后再把1右移
3. 代码
取反加一：
System.out.println((a&(~a+1)));
System.out.println((a&(-a)));
暴力：
private static int findRightest(int a) {
int rightPos = 0;
// 找最低位的1
for(int i = 0; i < 32; i++){
if((a & 1) == 1){
rightPos = i;
break;
}
a = a>>1;
}
a = 1;
// 右移
for (int i = 0; i < rightPos; i++) {
a = a << 1;
}
System.out.println(a);
return a;
}
2.3 找到两种奇数数
1. 题目
一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
2. 思路
全部异或，只留下eor = a^b
因为a != b，所以二进制的ab至少有一位不一样，即eor != 0，也就是至少存在一位为1。
既然有一位为1，代表a，b在这一位不同（异或：同0异1），那么就可以通过这一位来区分数组。
这一位为0的放一边，为1的放一边，分别异或，这样得到的数就可以区分出来ab了。
只要是eor有一位为1就可以区分，具体是哪个无所谓，所以不妨设是最右侧的一个。
3. 代码
private static int[] getAB(int[] arr) {
// 先异或，得到eor=a^b;
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
// 对于ab，最右侧一位的1提取出来
// System.out.println(eor);
int rightest = eor&(-eor);
// System.out.println(rightest);
// 根据这一位来区分属于谁
// 不妨设a在这位为0，b在这位为1
int[] ans = new int[2];
for (int i = 0; i < arr.length; i++) {
if((arr[i] & rightest) == 0){
ans[0] ^= arr[i];
}else{
ans[1] ^= arr[i];
}
}
return ans;
}
2.4 找到出现k次的数
1. 题目
一个数组中有一种数出现K次，其他数都出现了M次，M > 1, K < M，
要求：找到出现了K次的数，额外空间复杂度O(1)，时间复杂度O(N)
2. 思路
利用长度为32的数组，记录下每一位置出现1的次数，模M除K就得到二进制的所求数，再转为十进制。
3. 代码
private static int findKTimes(int[] arr, int m, int k) {
int[] times = new int[32];
// 记录所有数的32位的出现的次数
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < times.length; j++) {
if((arr[i]&(1<<j)) != 0){
times[j] ++;
}
}
}
// Arrays.stream(times).forEach(System.out::println);
// 所有数%m/k 得到的数组合成int
int ans = 0;
for (int i = 0; i < times.length; i++) {
times[i] = times[i]%m/k;
}
// 组合成int
for (int i = 0; i < times.length; i++) {
// cur = 1 1 0 1
// times = 1 0 1 1
ans += (times[i]<<i);
}
return ans;
}