什么叫做托爾狗查找算法？（是不是也可以叫去噪算法、異常識別算法）
哈哈哈，就是我亂扯的，我是為了引入一個數(shù)學(xué)概念（異或）瞎掰的！
先看背景
有這么一個世界，叫做萬象國，住在這里面的人都有一個唯一的歸宿，他（她）們窮極一生來找尋注定的那個TA，而且一定會找到。
這個世界有些奇怪的天諭（從誕生起就存在，從未看到過例外）：
- 總?cè)藬?shù)是偶數(shù)，在沒有找到生命中的那個TA時人是不會死的（因此在這個世界里面直男癌跟**女壽命特別長，夕陽斜下時總能看到TA們飽經(jīng)滄桑的眼神悠悠地望著遠(yuǎn)方），已經(jīng)結(jié)對的人總是在同一天一起離去。
- 這個世界中的人打招呼的方式是手執(zhí)手 "卍解" 操作，因?yàn)檫@在最開始是一種找尋真命天子的術(shù)式，后來慢慢演變成了打招呼的方式，假如是真命天子的話就會伴隨著一陣耀眼的光芒雙雙緩緩步入其中不知所蹤，人們都說那是去了天堂。
- 未知的神秘禁制......
突有一日，天邊紅霞如血，卻又天雷滾滾，一道晶光從天而降，同時伴隨著一陣清香而來（單身狗的清香）：
來了之后托爾蒙逼了，它的感覺是：
- 我是誰？
- 我在哪？
- 我要干啥？
腫么辦？一陣頭痛之后，突然記起先知告訴它回去的唯一辦法是在異次元找到那個唯一的她！當(dāng)時走的急，沒細(xì)想，此刻冷靜下來之后發(fā)現(xiàn)一個極大的BUG 啊?。?！
同時另一邊，萬象國的國防部長感知了空間波動，知道大概的方位：
“特勤組A1302去把入侵者抓回來?！?br>
“領(lǐng)命?！?/p>
但是部長不知道的是托爾的技能是啥？！是飛呀！是錘子??！因此一個半月過去了，半個人影，哦，不對，是半個狗影都沒找到！
地點(diǎn)：國防部；
“你們進(jìn)特訓(xùn)營重新定級......”
“（內(nèi)心os）啊~天吶！特訓(xùn)營什么的我再也不想去了??！那不是人待的地?。≡趺崔k怎么辦?。∮袥]有回旋的余地?。☆^！頭兒！趕緊說兩句??！&&%￥#￥#￥￥”
“下去！”
“嗯？完了？完了！??！”
眾人皆退下。
“把特腦小組叫來！”
不一會兒，一群頂著噌亮噌亮光環(huán)的人走上前來，待走近了才發(fā)現(xiàn)原來都是涂了油的光頭大師們！
“已知，一個數(shù)組里面有2n+1個數(shù)，除了一個數(shù)以外其他的都是一對一對出現(xiàn)的，請問你們采用何種策略可以找出這個奇異的數(shù)據(jù)出來？”部長大人如是問道。
“說人話！”光頭哥們脫口而咆哮。
“咳咳···我們國內(nèi)來了個異族份子，需要盡快找出，要是找的晚了！怕是···怕是會····”部長緩緩說到。
“怕是會怎樣?。∧愕故峭纯禳c(diǎn)一次說完??！不要給自己亂加戲啊！”眾人開啟了吐槽模式。
“會餓死的......”
“？？？?。?！我的刀呢！”
吐槽歸吐槽，干活歸干活，突然大廳一陣白光閃爍，每個光頭閃耀著白光，互相連接著，像是某種魔法法陣一樣交錯、旋轉(zhuǎn)跳躍，最終合成一股光線射向天際，像極了我30塊錢包郵買的LED點(diǎn)陣臺燈。
他們這個臺燈，(啊，呸~)是天合法陣，開始運(yùn)轉(zhuǎn)了，首先是建立模型?。?shí)際場景映射到數(shù)字空間（R空間），矩陣空間，然后你就可以利用數(shù)學(xué)這個強(qiáng)有力的工具來進(jìn)行玩耍啦！
光頭哥1號：
首先是分析問題背景，發(fā)現(xiàn)，唉，找個人出來，那還不簡單，我Duangduangduang一個一個比就好了嘛！那我們來算下哈！
假設(shè)總共有m個人，由于這個世界的特性，因此人數(shù)是成對的是偶數(shù)，因此可以設(shè)為2n，加上異鄉(xiāng)人就是2n+1個人了！
因此：m = 2n+1
那么我們首先隨便找一個出來：
“喂，你，對，就是你，不要看了就是你，長的這么矮還站在最后面，活該你出不了頭啊！”
然后我們再隨便找一個人：
“唉~旁邊的那個，長的帥的那個，麻煩你把褲子提好站出來！”
“好了，你們兩互相結(jié)個卍解??！”
“報告長官，我們都是鐵血真漢子??！我不結(jié)這么羞恥的??！”
“是啊，灑家寧死不從！”
“唉唉唉~我說你們兩個啊，這是官方例行檢查，你們照做就行了！再說了，在沒找到那個真命天子之前說不定你們都一直以為自己是個異性戀呢?。ù箪F）”
“·······”
“·······”
迷之安靜·····，卍解，結(jié)印失敗！
還好，還好不是，嚇?biāo)牢疫@個200斤的大寶寶了！
“是啊是?。『每膳?！”
“好了，矮子留下，長的帥的先退下，下一個”
“哄逗泥?。。《何夷兀。?！”
看到?jīng)]，就是這樣，最差的情況是在第n次找對那個結(jié)印陳功的人，結(jié)印成功后雙雙離去，總?cè)藬?shù)變成 2(n-1)+1,然后開始下一輪的檢測。
總結(jié)：
這種情況下是不是最差得2n2(n-1)2(n-2)····12=2^n*n!次測試！對啦這就是算法里面的時間復(fù)雜度啦,比O(n！)還大，時間老長了。
光頭哥2號：
“啊！不行啊，你這個太費(fèi)時間啦！我來出個主意！”
“我這里有個設(shè)備，能夠把每個人都映射出一個值來，有大有小各為不一，但是命中人的值跟你是一樣的，由于這個設(shè)備是史前神器，隨便使用會亂天道毀朝綱，因此只能用一次，而且只能秘密用！看過蝙蝠俠小丑篇嗎？就像那里面的聲納探測器一樣，太過逆天，它的存在就是對整個人類的不公，因此只有在此特殊情況下方能秘密使用，而且使用之后即會自行銷毀。”
“首先我把每個人的值映射出來，然后做一個排序，排完之后看下哪個值是單一的那不就是外星人么！而且我這種排序算法時間復(fù)雜度可以達(dá)到O(nlogn)，比你的不知快到哪里去了?。?！”
光頭老大哥：
Round 1
“偶豆豆們喲，你們不是老哥我的對手喲~”
來來來首先給你們普及點(diǎn)基礎(chǔ)知識：
還記得在萬象國皇家理工大學(xué)時大二上的數(shù)字電路課程嗎？
有個叫做異或的玩意兒！它長這樣⊕，洋文名叫exclusive OR，或縮寫成xor，寫代碼時用"^"代替。
當(dāng)時課堂上教我們的是：1⊕0=1 0⊕0=0 1⊕1=0也就知道電路里面相同狀態(tài)異或就是0，不同狀態(tài)之間異或就是1！
后來在數(shù)字電路計(jì)算的時候有：
==================================
交換律：A ⊕ B = B ⊕ A
結(jié)合律：A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C
A ⊕ 1 = A';
A ⊕ 0 = A;
A ⊕ A = 0;
A ⊕ A' = 1;
===================================
總結(jié)起來就是：相同的兩個值異或就是0，不同的兩個值異或就非0，0跟別的值異或則不影響其他值，這不是一個極其完美的特性么！我們隨便抽兩人進(jìn)行異或，是命中人，那么結(jié)果就是0，對后面不影響了，我接著去異或就好了啊直到結(jié)束，那么最終留下來的肯定就一定是那個外星人！??！
“光頭老大哥！我有問題！”
“小盆友請講！”
“你這個有先后關(guān)系的嘛？”
“小盆友，異或是滿足交換率的，比如：
A ^ B ^ C ^ B ^ C ^ D ^ A
= A ^ A ^ B ^ B ^ C ^ C ^ D
= 0 ^ 0 ^ 0 ^ D
= 0 ^ D
= D
看清楚沒有小盆友，無論你原來的順序是怎樣的，我都可以直接交換位置的，最終出來的一定是外星人D。”
“老大哥，我總感覺A ^ B ^A這樣的操作中，A ^ B 會使得B的特性變沒了，能給個具體的栗子嗎？”
“小朋友，請看：
我們隨便假設(shè)：A=0X51(01010001B)，B=0X8A(10001010B)
那么A ^ B就是：
01010001
⊕
10001010
---------
11011011
結(jié)果是0xDB，乍一看確實(shí)啊，把B值給整的面目全非都不成外星人形了！但是別慌，我們再來異或A算下：
11011011
⊕
01010001
---------
10001011
看?。?！快看?。。。∈遣皇亲兓谺（0x8A）了?。?！神不神奇！這就好比關(guān)二哥身曹營，心里系的全是劉大哥啊！
因此就算過五關(guān)斬六將，身中箭矢，備受猜忌，但其心依舊不變，但歸玄德，依舊是原來那個手持青龍偃月刀，溫酒斬梟將的關(guān)二爺！
代碼如下：
int singleDogger(int A[], int n) {
//特殊情況1,2
if(n<=0) return -1;
if(n==1) return A[0];
int dogger = 0;
for (int i = 0; i < n; i ++) {
dogger = dogger^ A[i];
}
return dogger;
}
”
“噢，那我懂了，這樣子的話我只要把這2n+1個值依次進(jìn)行異或就行，那么最后得到的肯定就是那個外星人！但是·····”
“喲呵~小伙子悟性不錯??！但是啥？但說無妨！”
“謝謝老哥夸獎，我想問的是要是突然又來了一個外星人可咋辦？”
“（&&（*￥@￥#￥&，小小書生，可懂得了否？”
“老哥，穩(wěn)！”
（具體如何解，請聽下回分解。）
Round 2
后來這個小書生回憶到，老哥解題的過程，可謂是蝦幾8優(yōu)化，扣細(xì)節(jié)?。∪鄙俚牟皇翘祚R行空的想法而是扣細(xì)節(jié)的心！
我們還是直接把2n+1個值進(jìn)行異或操作，那么最終得到的肯定是A^B嘛！這兩個外星人是不是這個世界的人？不是吧，那么他們肯定是卍解操作也即異或之后的結(jié)果不為0，既然不為0 的話，把這個值展開成二進(jìn)制，里面總有某個位置一個為0一個為1，比如你看：
假設(shè)：A = 0X01; B = 0X03; 那么A⊕B的值不為0把！展開成二進(jìn)制細(xì)細(xì)細(xì)細(xì)看一下： 0000 0001B ⊕ 0000 0011B ----------- 0000 0010B 看到?jīng)]有異或值不為零的話一定至少在某一位存在一個為1一個為0，如上面的在從右往左數(shù)第二位A對應(yīng)的是0，B對應(yīng)的是1。
好了，到這里我們知道這兩個外星人，噢不，外形狗的異或值在某一位一定存在不一樣的值，我們這里找到的是bit1位置（從最右的bit0開始數(shù)的），這樣子是不是分了兩個陣營了？既然陣營都分出來了，然后我們就可以叫大家集合了！
“啊，各位父老鄉(xiāng)親，麻煩大家抬起自己的右腳丫子，從右往左數(shù)第二根腳指頭指甲蓋有分叉的往左站，沒分叉的往右站！”
底下一片人頭攢動，熙熙攘攘，不出一會人稍安定，人群中就分出了一條道路，稀稀落落地掉著幾只鞋子...
“光頭隊(duì)，哦不，天機(jī)處煩請進(jìn)行處理。。。”
在光頭對分別對兩邊進(jìn)行異或操作之后，每邊都最終剩下一個人，沒錯啦，就是那兩個外星人！當(dāng)然咯，在我們找出第一組的外星人之后，第二組的還需要繼續(xù)一個個異或找嗎？我認(rèn)為是不需要的，因?yàn)槲覀円呀?jīng)知道A^B的值了，也知道其中一個的值了，那么我們將這兩個值再做一次異或那不就是另外一個值咯！
所以在實(shí)際寫代碼的時候，我們可以這樣取bit1=1這個特征，然后讓所有的值與00000010B進(jìn)與操作，操作完后不為零則進(jìn)行異或操作，這樣子一輪下來就自動分出兩類，且同時其中一個值就出來了，當(dāng)然了，另外一個外星人也呼之欲出。
“森賽！森賽！請問你為啥就認(rèn)定這么分類，那些命中人就都會被分在同一陣營呢？”
“小伙子，基礎(chǔ)知識不牢靠??！你想啊，既然是命中人，那么是不是展開成二進(jìn)制后的所有位都是相同的啊，既然相同，那么bit1位置肯定也相同啊，那么最終肯定會被分到同一陣營了的嘛！”
你看，順便把代碼也給你寫了：
int getFirstOneBit(int num) //輸出 num 的低位中的第一個 1 的位置
{
return num & ~(num - 1); // num 與 -num 相與找到
}
void findTwoDogger(int *array, int length){
int aXORb = 0;
int firstOneBit = 0;
int a = 0;
int b = 0;
for (int i = 0; i < length; i++) {
aXORb ^= array[i];
}
assert(aXORb != 0); //保證題目要求，有兩個single的數(shù)字
firstOneBit = getFirstOneBit(aXORb);
for (int i = 0; i < length; ++i) {
if(array[i] & firstOneBit) {
a ^= array[i];
}
}
b = aXORb ^ a;
cout << "a: " << a << endl;
cout << "b: " << b << endl;
}
int main()
{
int array1[] = {2, 5, 8, 2, 5, 8, 6, 7};
findTwoDogger(array1, 8);
return 0;
}
Round 3
吃瓜群眾x：那要是來了三個外星人呢？
老大哥：你咋不上天呢？
沒辦法，老大哥為了維持自己的尊嚴(yán)及地位，必須腆著老臉繼續(xù)掰。
我們?nèi)?x = a^b^c，可以獲取到的情報是X不為a,b,c中的任意一值。
我們可以反證嘛！假如 x=a，那么x^a = a^a = 0 = a^a^b^c = b^c = 0,而我們的前提條件是啥？！是這三個外形人都是不同的啊！用術(shù)語表示就是在這個數(shù)組中只出現(xiàn)過一次的數(shù)字啊！b^c=0都表示相同了好嘛！其他同理。由于三個數(shù)都是唯一出現(xiàn)的所以x^a = b^c 結(jié)果肯定是非零的，其他同理，那么f(x^a)的值也肯定是非零;
我們設(shè)定函數(shù)f(x)，他的功能是找到自變量x的第一bit位置。我們能得到的情報是f(x^a)、f(x^b)、f(x^c)得到的值肯定都不為0；
我們這里假設(shè):
X = x^a = b^c
Y = x^b = a^c
Z = x^c = a^b
有X^Y^Z = 0，那么就一定有 X、Y、Z 三個數(shù)的低位起第一位為1的位置兩個相同，一個不同； 比如 ：
X: 00001000
Y: 00000100
Z: 00001100
Y和Z的低位第一位都是00000100， X的低位第一位是00001000；而且看到?jīng)]有一定是兩個1和一個0喲！而不是兩個0和一個1，否則就不會有異或結(jié)果為0啦！
我們把X、Y、Z的最低1的位置找出來后，找出那個位置不一樣的就是唯一的那個咯！
比如上面的X,找出X的最低位置之后是不是就可以以此位為分類標(biāo)準(zhǔn)，將此位為1的分一類，為0的分一類，
然后將為1的那一類進(jìn)行異或得到的就是我們要找的外星人啦！這個找到后那么剩下的兩個外星人就是上面的找兩個問題啦！。
》總結(jié)：利用了X^Y^Z = 0則有最低為1的位置具有兩個相同一個不同的特性（見上面XYZ的示例），然后就構(gòu)建出這樣的表達(dá)式，然后利用一些小trick來實(shí)現(xiàn)最終目的，很棒棒！。
python代碼如下：
def getfirstonebit(num):
return num & ~(num - 1)
def findTwoDogger(array,length):
a_XOR_b = 0
firstonebit = 0
a = 0
b = 0
for i in range(length):
a_XOR_b ^= array[i]
assert a_XOR_b != 0
firstonebit = getfirstonebit(a_XOR_b)
for i in range(length):
if array[i] & firstonebit:
a ^= array[i]
b = a_XOR_b ^ a
print("a = %d, b = %d"%(a, b))
def findoneDogger(array,length):
a_XOR_b_XOR_c = 0
c = 0
firstonebit = 0
for i in range(length):
a_XOR_b_XOR_c ^= array[i]
for i in range(length):
#使用異或排除掉不相干的元素
#簡化為getFirstOneBit(a ^ b) ^ getFirstOneBit(a ^ c) ^ getFirstOneBit(b ^ c);
firstonebit ^= getfirstonebit(a_XOR_b_XOR_c ^ array[i])
for i in range(length):
if getfirstonebit(a_XOR_b_XOR_c ^ array[i]) == firstonebit:
c ^= array[i]
print("c = %d"%(c))
return c
if __name__ == "__main__":
#先找出一個來，然后再找出另外兩個
array1 = [9, 5, 8, 9, 5, 8, 1, 2, 3]
c = findoneDogger(array1, len(array1))
array2 = [9, 5, 8, 9, 5, 8, 1, 2, 3, c]
findTwoDogger(array2,len(array2))
結(jié)果如下：
c = 2
a = 3, b = 1
“老哥，代碼看不懂咋辦？”
“小兄弟我都給你轉(zhuǎn)成python版本了，你還看不懂??？！那我估計(jì)，你是被里面的邏輯及寫法繞暈了！來我給你捋一捋！”
“?。≡劭创a啊，得講究個從上而下，先骨架后血肉，跟重構(gòu)一個復(fù)雜信號一樣的先把低頻信號架起來，然后再貼上一些高頻信號補(bǔ)充細(xì)節(jié)！”
首先你看，從main入口這里顯示找到一個外星人，然后再找另外兩個外形人，這就是先畫出一個整體思路啦！
然后咱們再走進(jìn)去findoneDogger(array1, len(array1))看看里面是如何實(shí)現(xiàn)的：
首先無非是定義一些變量嘛，我們?nèi)齻€外星人的異或值假設(shè)為a_XOR_b_XOR_c，先要被找到的外星人命名為c，我們的核心關(guān)鍵信息就是每個數(shù)字的第一個出現(xiàn)1的位置啊，那我們就定義為firstonebit就好了！變量都對應(yīng)初始化為0，為啥是0呢？因?yàn)?跟任何數(shù)進(jìn)行異或還是那個數(shù)?。∫簿褪?是純凈的！
第一步干啥呢？還是跟原先一樣把所有的值進(jìn)行異或操作，得到的值肯定是abc?。。ㄗ⒁鈫?，這里就算是為0，也是可以把這三個外星小崽子找出來的！為0是啥意思呢？為0就是說找了一圈發(fā)現(xiàn)一點(diǎn)異常也沒有，跟沒人來過一樣！畢竟我們是根據(jù)全部異或來獲取線索的嘛?。?/p>
第二步來了，這一步我們要干的是分別找出a^b,b^c,c^a的最低一位位置，然后將這三個值進(jìn)行異或來確定三個組合中哪個屬于異類！
到這里就有點(diǎn)麻煩了！我們怎么得到這三個組合的最低位置呢？
- 我們分析下哈，我們已知的是a^b^c，但是這并沒有什么暖用?。”热缯f最低位為1的位置找出來也沒啥用?。∵@是三個數(shù)了！不是非此即彼的關(guān)系了！
- 還記得之前的論述的三個數(shù)異或?yàn)?就有某種特性嗎？
不記得沒關(guān)系！我再給你啰嗦一遍：
假如存在 X^Y^Z = 0，那么一定存在其中兩個數(shù)的最低1位置是相同的，而剩下那個的最低位是不同的！
你看假如存在：X:00000100 Y:00000110 Z:00000010這三個數(shù)是不是異或完之后結(jié)果為0！而且你發(fā)現(xiàn)沒有，從低位起往左數(shù)，第一個出現(xiàn)1的位置，必須是兩個1一起出現(xiàn)，否則是不存在全部異或結(jié)果為0的！這就是一個核心的特征??！
從這里又突然聯(lián)想到，機(jī)器學(xué)習(xí)是人為地找特征來分類，實(shí)際上使用的是人的腦力！而深度學(xué)習(xí)卻是動用強(qiáng)大的計(jì)算機(jī)算力結(jié)合一個算法框架來找到最合適的特征，我們?nèi)藶檎页龅慕鉀Q方案很有可能只是局部最優(yōu)解而不是全局最優(yōu)解，而深度學(xué)習(xí)卻是盡力去尋找那個全局最優(yōu)的，深度學(xué)習(xí)的目的是找到那個能描述你的特征來盡可能地認(rèn)出你來?。。?/code>
- 現(xiàn)在我們要做的就是把這個特性給利用起來，令M=a^b^c,那么就有：(M^a)^(M^b)^(M^c) = (b^c)^(a^c)^(a^b) = 0這樣子是不是就構(gòu)建出來了三個變量的異或值為零了！
設(shè)：
X = M^a
Y = M^b
Z = M^c
- 具體代碼中如何實(shí)現(xiàn)呢？我們最終要的就是X = (b^c)、Y = (a^c)、Z = (a^b)三個值的第一個位置！我們不是可以得到a^b^c的值嘛！這是一個定值M嘛！我拿這個定值跟所有的值都異或一次并取最低位，那么我們就可以得到兩個陣營，下圖中的左右兩個陣營：原本成對的數(shù)在異或M之后的值還是一樣的嘛！取低位當(dāng)然還是一樣了！左邊這個大圈里面就是了，有n對；而那三個外星人與M異或之后取低位肯定會出現(xiàn)兩個1位置一樣，而剩余一個不一樣，大概就如右邊這個小框內(nèi)的數(shù)字一樣！
好了現(xiàn)在我們把這些值全部異或一下，最后得到的是不是就是00010000了！**就是說三個外星人其中一個的bit4 = 1。
for i in range(length):
#使用異或排除掉不相干的元素
#化簡為: getFirstOneBit(a ^ b) ^
# getFirstOneBit(a ^ c) ^
# getFirstOneBit(b ^ c);
firstonebit ^= getfirstonebit(a_XOR_b_XOR_c ^ array[i])
那么我再把所有人召集起來，用M值依次對之進(jìn)行異或操作并取低位，低位為bit4的作為一組，然后將這組的值進(jìn)行異或那么得到豈不就是其中一個外星人咯?。?！完美！
for i in range(length):
if getfirstonebit(a_XOR_b_XOR_c ^ array[i]) == firstonebit:
c ^= array[i]
- 剩下的就是找找兩個外星人的套路了！easy，順便說下，之前還考慮到假如a^b^c = 0怎么辦？因?yàn)榭偟囊惠啴惢蛳聛斫Y(jié)果是0啊，說明完全正常啊！雖然我知道不正常但是卻沒有一點(diǎn)點(diǎn)線索的感覺！實(shí)際上無論是否為0我們都能利用這個隱含條件完美地找出了外星人！只能說，人類的智慧真的是太無窮無盡了！只要你敢想、敢用心！
終于寫完了！結(jié)于2017/11/10 0:27AM，寫這些算法類的東西真的很開心！算法即人類的智慧是如此的美妙！當(dāng)是終生追求！將算法融入生活，好好學(xué)習(xí)，好好生活，晚安！
參考：
https://www.lijinma.com/blog/2014/05/29/amazing-xor/
http://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96
http://yjq24.blogbus.com/logs/41863963.html
http://wzw19191.blog.163.com/blog/static/131135470200992610551971/
http://kapok.blog.51cto.com/517862/129941
http://blog.csdn.net/huxian370/article/details/8024416
http://www.cnblogs.com/Ivony/archive/2009/07/23/1529254.html
http://blog.chinaunix.net/uid-20937170-id-3407361.html
http://blog.csdn.net/yfkiss/article/details/11775569
http://blog.sina.com.cn/s/blog_88c9ddc50101810p.html
