好记性不如烂笔头
一，异或用法：
1.不借用变量前提，交换两数值？
a = a ^ b;
b = a ^ b;
a = a ^ b;
2.数组中只有一个数出现奇数次，其余数都出现了偶数次，怎么找到这个数？
public static int findOne(int[] arr){
int a = 0;
for(int i=0;i<arr.length;i++){
a ^= arr[i];
}
return a;
}
3.提供有一个int数，提取其最右侧第一个1 （a&（~a+1））
记住定律 a&(-a) 结果是右侧第一个数为1，其余为0的数（二进制）
4.一个数组有两个数出现奇数次，其他都出现偶数次，求这两个数（需要需用2，3的结论）
//假设a,b为这两个奇数次数，原理就是先异或，求出结果eor = a^b
//可以得出结论eor必定不为0，说明二进制位必定有一位为1
//找到最右侧1的位rightOne利用3.的知识点
//可以得出结论a,b必定分属两个阵营，如果a的rightOne为1，那么b的肯定为0
//同理剩余的出现的偶数次的数他们也可以被分成这两个阵营
//再利用a去异或自己阵营的这些偶数次的数可以得到a=eor`，b则等于eor^eor`
public static void findTwo(int[] arr){
int eor = 0; //eor其实就是a^b
for(int i=0;i< arr.length;i++){
eor ^=arr[i];
}
int rightOne = eor&(-eor);
int onlyOne = 0 ; //eor'
for(int i=0;i<arr.length;i++){
if((arr[i]&rightOne)!=0){ //说明arr[i]和rightOne的1重叠到了，就可以划出阵营
onlyOne ^= arr[i];
}
}
System.out.println("一个是"+onlyOne+"另一个是"+(onlyOne^eor));
}
5.一个数组中有一个数出现了K次，其他数出现了M次，已知M>1,K<M，求出出现K次的数的值，要求空间复杂度O(1),时间复杂度O(n)
/**
解题思路：整型数int是32位字节的，我们开辟一个长度为32的数组，里面暂时全放0
然后将出先K次的数二进制上出现了1的位置加到数组里面，同理M也将二进制位出现了1的数加到数组
最后出现的数组可能就类似[...a],假设数组最后一位等于a,说明a的组成成分可能有K也可能有M
如果有K，那么用a%M则必不可能=0，同理，如果a%M=0说明此处K的二进制位0，
则我们就可以根据求余%运算推导出最后的k的二进制表示从而算出K为多少
*/
public static void findK(int[] arr,int k,int m){
int[] a = new int[32]; //定义32位的数组
for(int num : arr){
for (int i = 0; i < 32; i++) { //这个是常数次循环，所以是O(1)
if(((num>>i)&1)!=0){ //这里((num>>i)&1)!=0说明num第i位上的数是1
a[i]++; //可以写成a[i]+=((num>>i)&1),就不需要if语句
}
}
}
int answer = 0; //结果值
for(int i=0;i<32;i++){
if(a[i]%m!=0){ //求余，如果不等于0说明此处K有1
answer |=(1<<i); //则将1左移i位平且和answer做或运算，并且并入answer中
} //循环32次结束后，1都填上后就是k的二进制值表示方法
}
System.out.println(answer);
}
