0. 一個(gè)整數(shù)N的二進(jìn)制表示中有多少個(gè)1辐怕，最低位的1出現(xiàn)在第幾個(gè)位置搂漠。
1. 交換兩個(gè)整數(shù)而不必使用第三個(gè)參數(shù)
a=9;
b=11;
a=a^b;
b=a^b;
a=a^b;
//a=11,b=9;
2. 使用異或來判斷一個(gè)二進(jìn)制數(shù)中的1的數(shù)量是奇數(shù)還是偶數(shù)。
- 求10100001中的1的數(shù)量是奇數(shù)還是偶數(shù);1010000^1 =1，結(jié)果為1就是奇數(shù)個(gè)1摧冀，結(jié)果為0就是偶數(shù)個(gè)1;應(yīng)用：這條性質(zhì)可以用于奇偶校驗(yàn)(Parity Check),比如在串口通信中，每一個(gè)字節(jié)的數(shù)據(jù)都計(jì)算一個(gè)校驗(yàn)位系宫，數(shù)據(jù)和校驗(yàn)位一起發(fā)送出去索昂，這樣接收方可以根據(jù)校驗(yàn)位粗略的判斷接收到的數(shù)據(jù)是否有誤。
3. 快數(shù)比較兩個(gè)值
- 判斷兩個(gè)int型數(shù)字是否相等扩借，你肯定會(huì)想到判斷(a-b)==0(使用a==b和a^b == 0的效果是一樣的椒惨。)，但是使用a^b==0效率會(huì)更高潮罪。
4. 在匯編中經(jīng)常使用：xor a,a將變量置零
5. 校驗(yàn)和恢復(fù)
- 校驗(yàn)和恢復(fù)主要利用的了異或的特性：IF a ^ b = c THEN a ^ c = b
應(yīng)用：一個(gè)很好的應(yīng)用實(shí)例是RAID5康谆，使用3塊磁盤（A、B嫉到、C）組成RAID5陣列沃暗，當(dāng)用戶寫數(shù)據(jù)時(shí)，將數(shù)據(jù)分成兩部分何恶，分別寫到磁盤A和磁盤B孽锥，A ^ B的結(jié)果寫到磁盤C；當(dāng)讀取A的數(shù)據(jù)時(shí)细层，通過B ^ C可以對A的數(shù)據(jù)做校驗(yàn)忱叭，當(dāng)A盤出錯(cuò)時(shí)隔崎，通過B ^ C也可以恢復(fù)A盤的數(shù)據(jù)。RAID5的實(shí)現(xiàn)比上述的描述復(fù)雜多了韵丑，但是原理就是使用 異或爵卒，有興趣的同學(xué)看下RAID5
6. 互換二進(jìn)制數(shù)的奇偶位
- 寫一個(gè)宏定義，實(shí)現(xiàn)功能位將一個(gè)int型的數(shù)的奇偶位互換如00000110(6)->00001001(9)輸出為9.
#define N(n) ((n<<1)&(0xAAAA)) | ((n>>1)&(0x5555))
7.最常出現(xiàn)的面試題: 一個(gè)整形數(shù)組里除了N個(gè)數(shù)以外撵彻，其他的數(shù)都出現(xiàn)了兩次钓株，找出這N個(gè)數(shù)。
(1):題目(LeetCode中通過率最高的一道題)Single Number:Given a array of integers,every element appears twice except for one.Find that single one.
由于異或的交換律(a^ b ^ c ^ d = a ^b ^ d^c),所以對于上題對整個(gè)數(shù)組中的每一個(gè)數(shù)進(jìn)行異或操作陌僵，結(jié)果就是那個(gè)剩余的為單的數(shù)字轴合。（A ^B ^C ^B ^C ^D ^D = A ^B ^B ^C ^C ^D ^D）.(2): 一個(gè)整型數(shù)組里面除了兩個(gè)數(shù)之外，其他的所有的數(shù)字都出現(xiàn)了兩次碗短。
第一步：假設(shè)為a,b對所有數(shù)字異或之后得到的結(jié)果就是a^b的結(jié)果受葛。
第二步：想辦法得到a或者b，假設(shè)a^b為00001001偎谁，值為1的位表示a和b在這一位上不同总滩，如上則表示a和b在最低位上不同。所以我們找出所有最低位為1的數(shù)進(jìn)行異或巡雨，得到的就是a或者是b闰渔。
第三步：假設(shè)我們已經(jīng)找到了a，則b=a(ab),這樣我們就找到了b,所以我們需要循環(huán)兩次铐望；
//宏定義冈涧，用來找出某個(gè)數(shù)第一次bit為1的地方、
//如 10010110 則運(yùn)算結(jié)果為 00000010
#define getFisrtOneBit(N) ((N) & ~(N-1))
int findTwo(int *array,int len)
{
int i = 1;
int aXORb = array[0];
int a = 0;
int b = 0;
int firstOneBit = 0;
for (; i < len; ++i)
aXORb^=array[i];
if (aXORb==0)
return 0;
firstOneBit = getFisrtOneBit(aXORb);
for (i = 0; i < len; ++i){
if(array[i] & firstOneBit)
a^=array[i];
}
b = aXORb^a;
printf("%d\n", a);
printf("%d\n", b);
return 0;
}
- (3): 一個(gè)整型數(shù)組里除了三個(gè)數(shù)之外正蛙，其他的數(shù)字都出現(xiàn)了兩次督弓，請寫程序找出這三個(gè)只出現(xiàn)一次的數(shù)字。
第一步：像上面一樣全部進(jìn)行異或 則得到result = X^ Y ^Z乒验；
第二步：把問題簡化為：假設(shè)一個(gè)數(shù)組中有三個(gè)不同的數(shù)字X,Y,Z愚隧；已知result = X ^Y ^Z,求X，Y徊件，Z奸攻？
1). 假設(shè)X^ Y^ Z = 0蒜危；則XYZ三個(gè)數(shù)的低位第一位為1的位置有兩個(gè)數(shù)相同虱痕，一個(gè)不同。例如：X:00001000辐赞，Y:00000100部翘，Z:00001100 Y和Z的低位第一位都是00000100,X的低位第一位是00001000;
2). (result^ X)^ (result^ Y)^ (result ^Z) = 0;所以三個(gè)數(shù)(result X)、(result Y)响委、(result^ Z)的低位第一位為1的位置有兩個(gè)相同新思，一個(gè)不同窖梁；那么我們獲取這三個(gè)數(shù)的低位第一位為1的位置后，進(jìn)行異或并取低位第一位為1的位置夹囚，就可以找到三個(gè)中"一個(gè)不同"的低位第一位為1的位置纵刘，假設(shè)這個(gè)值為firstOneBit。
3). 遍歷這三個(gè)數(shù)(result^ X),(result ^Y),(result ^Z),如果發(fā)現(xiàn)某個(gè)數(shù)的異或result等于firstOneBit,那么這個(gè)數(shù)就是"一個(gè)不同"的那個(gè)數(shù)荸哟。
4). 找到了一個(gè)數(shù)假哎，剩下的兩個(gè)數(shù)，就可以通過上面的方法找出鞍历。
第三步：完成第二步的簡化后舵抹，回到原題，我們的原題比簡化的問題多了一個(gè)成對的數(shù)據(jù)干擾劣砍，我們可以使用異或出去干擾數(shù)據(jù)惧蛹。
#define getFisrtOneBit(N) ((N) & ~( (N)-1))
int findOne(int *array,int len)
{
int aXORbXORc = 0;
int c = 0;
int firstOneBit = 0;
for (int i = 0; i < len; ++i)
aXORbXORc ^= array[i];
for (int i = 0; i < len; ++i)
firstOneBit ^= getFisrtOneBit(aXORbXORc ^ array[i]);
//使用異或會(huì)排除掉不相干的元素
firstOneBit = getFisrtOneBit(firstOneBit);
//獲取到最低位
for (int i = 0; i < len; ++i){
if (getFisrtOneBit(aXORbXORc ^ array[i]) == firstOneBit){
c ^= array[i];
}
}
printf("C:%d\n",c);
return c;
}
int findTwo(int *array,int len)
{
int i = 1;
int aXORb = array[0];
int a = 0;
int b = 0;
int firstOneBit = 0;
for (; i < len; ++i)
aXORb ^= array[i];
if (aXORb == 0)
return 0;
firstOneBit = getFisrtOneBit(aXORb);
for (i = 0; i < len; ++i)
{
if(array[i] & firstOneBit)
a^=array[i];
}
b = aXORb^a;
printf("%d\n", a);
printf("%d\n", b);
return 0;
}
int findThree(int *array,int len)
{
int tmpInt = findOne(array,len);
int *tmpBuf = (int *)malloc((len+1)*sizeof(int));
for (int i = 0; i < len; ++i)
tmpBuf[i] = array[i];
tmpBuf[len] = tmpInt;
findTwo(tmpBuf,len+1);
free(tmpBuf);
return 1;
}
