異或的性質
1.異或的本質是 無進位相加->相同為0,不同為1
2.異或的性質 a^a=0, a^0=a 以及交換律,結合率
異或的新用法:
1.不占用額外空間的交換位置a<->b
a=a^b;
b=a^b;
a=a^b;
2.一個陣列中一個數出現奇數次,其他數出現偶數次,通過異或找到該奇數次的數
[偽代碼]
a[n];
auto eor=0;
for(i from 0 to n)eor=eor^a[i];
因為交換律和結合律,偶數次的數經過異或后結果是0,最終運算式為奇數次的數an^0=an
3.一個陣列中兩個數出現奇數次,其他數出現偶數次,也可以通過異或找到該奇數次的數(進階)
原理:
篩選數:
如何得到eof`?
[偽代碼]
a[n];
int eor=0,eor`=0;
for(i from 0 to n)eor=eor^a[i];
int RightOne= eor&(~eor+1);//得到一個篩選數,該數可以篩選出第X位為1的數
for(int cur:a[n])
if(a[n]&RightOne!=0)eor`=(eor`)^a[n];//此時第X為1的數被異或進eor`,但偶數次數的相抵消為0,eor`存的是a或者b中第X位為1的那個數
eof=eof^eof`;//a^b^a=b,另一個數.即eof和eof`分別保存了兩個次數為1的數
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412986.html
標籤：其他
上一篇：演算法競賽——最短路問題