好記性不如爛筆頭
一，異或用法：
1.不借用變量前提滑废，交換兩數(shù)值蝗肪？
a = a ^ b;
b = a ^ b;
a = a ^ b;
2.數(shù)組中只有一個數(shù)出現(xiàn)奇數(shù)次袜爪，其余數(shù)都出現(xiàn)了偶數(shù)次蠕趁，怎么找到這個數(shù)？
public static int findOne(int[] arr){
int a = 0;
for(int i=0;i<arr.length;i++){
a ^= arr[i];
}
return a;
}
3.提供有一個int數(shù)辛馆，提取其最右側(cè)第一個1 （a&（~a+1））
記住定律 a&(-a) 結(jié)果是右側(cè)第一個數(shù)為1俺陋，其余為0的數(shù)（二進(jìn)制）
4.一個數(shù)組有兩個數(shù)出現(xiàn)奇數(shù)次，其他都出現(xiàn)偶數(shù)次昙篙，求這兩個數(shù)（需要需用2腊状，3的結(jié)論）
//假設(shè)a,b為這兩個奇數(shù)次數(shù)，原理就是先異或苔可，求出結(jié)果eor = a^b
//可以得出結(jié)論eor必定不為0缴挖，說明二進(jìn)制位必定有一位為1
//找到最右側(cè)1的位rightOne利用3.的知識點(diǎn)
//可以得出結(jié)論a,b必定分屬兩個陣營，如果a的rightOne為1焚辅，那么b的肯定為0
//同理剩余的出現(xiàn)的偶數(shù)次的數(shù)他們也可以被分成這兩個陣營
//再利用a去異或自己陣營的這些偶數(shù)次的數(shù)可以得到a=eor`映屋，b則等于eor^eor`
public static void findTwo(int[] arr){
int eor = 0; //eor其實(shí)就是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.一個數(shù)組中有一個數(shù)出現(xiàn)了K次同蜻，其他數(shù)出現(xiàn)了M次棚点，已知M>1,K<M，求出出現(xiàn)K次的數(shù)的值湾蔓，要求空間復(fù)雜度O(1),時(shí)間復(fù)雜度O(n)
/**
解題思路：整型數(shù)int是32位字節(jié)的瘫析，我們開辟一個長度為32的數(shù)組，里面暫時(shí)全放0
然后將出先K次的數(shù)二進(jìn)制上出現(xiàn)了1的位置加到數(shù)組里面默责，同理M也將二進(jìn)制位出現(xiàn)了1的數(shù)加到數(shù)組
最后出現(xiàn)的數(shù)組可能就類似[...a],假設(shè)數(shù)組最后一位等于a,說明a的組成成分可能有K也可能有M
如果有K贬循，那么用a%M則必不可能=0，同理桃序，如果a%M=0說明此處K的二進(jìn)制位0杖虾，
則我們就可以根據(jù)求余%運(yùn)算推導(dǎo)出最后的k的二進(jìn)制表示從而算出K為多少
*/
public static void findK(int[] arr,int k,int m){
int[] a = new int[32]; //定義32位的數(shù)組
for(int num : arr){
for (int i = 0; i < 32; i++) { //這個是常數(shù)次循環(huán)，所以是O(1)
if(((num>>i)&1)!=0){ //這里((num>>i)&1)!=0說明num第i位上的數(shù)是1
a[i]++; //可以寫成a[i]+=((num>>i)&1),就不需要if語句
}
}
}
int answer = 0; //結(jié)果值
for(int i=0;i<32;i++){
if(a[i]%m!=0){ //求余葡缰，如果不等于0說明此處K有1
answer |=(1<<i); //則將1左移i位平且和answer做或運(yùn)算亏掀，并且并入answer中
} //循環(huán)32次結(jié)束后忱反，1都填上后就是k的二進(jìn)制值表示方法
}
System.out.println(answer);
}
