外星狗搜寻算法！

作者: 十曰立 | 来源:发表于2017-11-07 20:21 被阅读18次

什么叫做托尔狗查找算法？（是不是也可以叫去噪算法、异常识别算法）
哈哈哈，就是我乱扯的，我是为了引入一个数学概念（异或）瞎掰的！

先看背景

有这么一个世界，叫做万象国，住在这里面的人都有一个唯一的归宿，他（她）们穷极一生来找寻注定的那个TA，而且一定会找到。
这个世界有些奇怪的天谕（从诞生起就存在，从未看到过例外）：

总人数是偶数，在没有找到生命中的那个TA时人是不会死的（因此在这个世界里面直男癌跟**女寿命特别长，夕阳斜下时总能看到TA们饱经沧桑的眼神悠悠地望着远方），已经结对的人总是在同一天一起离去。
这个世界中的人打招呼的方式是手执手 "卍解" 操作，因为这在最开始是一种找寻真命天子的术式，后来慢慢演变成了打招呼的方式，假如是真命天子的话就会伴随着一阵耀眼的光芒双双缓缓步入其中不知所踪，人们都说那是去了天堂。
未知的神秘禁制......

突有一日，天边红霞如血，却又天雷滚滚，一道晶光从天而降，同时伴随着一阵清香而来（单身狗的清香）：

来了之后托尔蒙逼了，它的感觉是：

我是谁？
我在哪？
我要干啥？

肿么办？一阵头痛之后，突然记起先知告诉它回去的唯一办法是在异次元找到那个唯一的她！当时走的急，没细想，此刻冷静下来之后发现一个极大的BUG 啊！！！

同时另一边，万象国的国防部长感知了空间波动，知道大概的方位：
“特勤组A1302去把入侵者抓回来。”
“领命。”

但是部长不知道的是托尔的技能是啥？！是飞呀！是锤子啊！因此一个半月过去了，半个人影，哦，不对，是半个狗影都没找到！

地点：国防部；
“你们进特训营重新定级......”
“（内心os）啊~天呐！特训营什么的我再也不想去了啊！那不是人待的地啊！怎么办怎么办啊！有没有回旋的余地啊！头！头儿！赶紧说两句啊！&&%￥#￥#￥￥”
“下去！”
“嗯？完了？完了！！！”

众人皆退下。

“把特脑小组叫来！”

不一会儿，一群顶着噌亮噌亮光环的人走上前来，待走近了才发现原来都是涂了油的光头大师们！

“已知，一个数组里面有2n+1个数，除了一个数以外其他的都是一对一对出现的，请问你们采用何种策略可以找出这个奇异的数据出来？”部长大人如是问道。

“说人话！”光头哥们脱口而咆哮。

“咳咳···我们国内来了个异族份子，需要尽快找出，要是找的晚了！怕是···怕是会····”部长缓缓说到。

“怕是会怎样啊！你倒是痛快点一次说完啊！不要给自己乱加戏啊！”众人开启了吐槽模式。

“会饿死的......”

“？？？！！！我的刀呢！”

吐槽归吐槽，干活归干活，突然大厅一阵白光闪烁，每个光头闪耀着白光，互相连接着，像是某种魔法法阵一样交错、旋转跳跃，最终合成一股光线射向天际，像极了我30块钱包邮买的LED点阵台灯。

他们这个台灯，(啊，呸~)是天合法阵，开始运转了，首先是建立模型啊！将实际场景映射到数字空间（R空间），矩阵空间，然后你就可以利用数学这个强有力的工具来进行玩耍啦！

光头哥1号：

首先是分析问题背景，发现，唉，找个人出来，那还不简单，我Duang_duangduang一个一个比就好了嘛！那我们来算下哈！
假设总共有m个人，由于这个世界的特性，因此人数是成对的是偶数，因此可以设为2n，加上异乡人就是2n+1个人了！

因此：m = 2n+1

那么我们首先随便找一个出来：

“喂，你，对，就是你，不要看了就是你，长的这么矮还站在最后面，活该你出不了头啊！”

然后我们再随便找一个人：

“唉~旁边的那个，长的帅的那个，麻烦你把裤子提好站出来！”
“好了，你们两互相结个卍解印！”
“报告长官，我们都是铁血真汉子啊！我不结这么羞耻的印！”
“是啊，洒家宁死不从！”
“唉唉唉~我说你们两个啊，这是官方例行检查，你们照做就行了！再说了，在没找到那个真命天子之前说不定你们都一直以为自己是个异性恋呢！（大雾）”
“·······”
“·······”

迷之安静·····，卍解，结印失败！

还好，还好不是，吓死我这个200斤的大宝宝了！
“是啊是啊！好可怕！”

“好了，矮子留下，长的帅的先退下，下一个”

“哄逗泥！！！逗我呢！！！”

看到没，就是这样，最差的情况是在第n次找对那个结印陈功的人，结印成功后双双离去，总人数变成 2(n-1)+1,然后开始下一轮的检测。

总结：

这种情况下是不是最差得2n2(n-1)2(n-2)····12=2^n*n!次测试！对啦这就是算法里面的时间复杂度啦,比O(n！)还大，时间老长了。

光头哥2号：

“啊！不行啊，你这个太费时间啦！我来出个主意！”

“我这里有个设备，能够把每个人都映射出一个值来，有大有小各为不一，但是命中人的值跟你是一样的，由于这个设备是史前神器，随便使用会乱天道毁朝纲，因此只能用一次，而且只能秘密用！看过蝙蝠侠小丑篇吗？就像那里面的声纳探测器一样，太过逆天，它的存在就是对整个人类的不公，因此只有在此特殊情况下方能秘密使用，而且使用之后即会自行销毁。”

“首先我把每个人的值映射出来，然后做一个排序，排完之后看下哪个值是单一的那不就是外星人么！而且我这种排序算法时间复杂度可以达到O(nlogn)，比你的不知快到哪里去了！！！”

光头老大哥：

Round 1

“偶豆豆们哟，你们不是老哥我的对手哟~”
来来来首先给你们普及点基础知识：

还记得在万象国皇家理工大学时大二上的数字电路课程吗？
有个叫做异或的玩意儿！它长这样⊕，洋文名叫exclusive OR，或缩写成xor，写代码时用"^"代替。
当时课堂上教我们的是：
1⊕0=1
0⊕0=0
1⊕1=0
也就知道电路里面相同状态异或就是0，不同状态之间异或就是1！
后来在数字电路计算的时候有：
==================================
交换律：A ⊕ B = B ⊕ A
结合律：A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C
A ⊕ 1 = A';
A ⊕ 0 = A;
A ⊕ A = 0;
A ⊕ A' = 1;
===================================
总结起来就是：相同的两个值异或就是0，不同的两个值异或就非0，0跟别的值异或则不影响其他值，这不是一个极其完美的特性么！我们随便抽两人进行异或，是命中人，那么结果就是0，对后面不影响了，我接着去异或就好了啊直到结束，那么最终留下来的肯定就一定是那个外星人！！！

“光头老大哥！我有问题！”
“小盆友请讲！”
“你这个有先后关系的嘛？”
“小盆友，异或是满足交换率的，比如：

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的特性变没了，能给个具体的栗子吗？”
“小朋友，请看：

我们随便假设：A=0X51(01010001B)，B=0X8A(10001010B)
那么A ^ B就是：

01010001
⊕
10001010
---------
11011011

结果是0xDB，乍一看确实啊，把B值给整的面目全非都不成外星人形了！但是别慌，我们再来异或A算下：

11011011
⊕
01010001
---------
10001011

看！！！快看！！！！是不是变回B（0x8A）了！！！神不神奇！这就好比关二哥身曹营，心里系的全是刘大哥啊！
因此就算过五关斩六将，身中箭矢，备受猜忌，但其心依旧不变，但归玄德，依旧是原来那个手持青龙偃月刀，温酒斩枭将的关二爷！

代码如下：

    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个值依次进行异或就行，那么最后得到的肯定就是那个外星人！但是·····”

“哟呵~小伙子悟性不错啊！但是啥？但说无妨！”

“谢谢老哥夸奖，我想问的是要是突然又来了一个外星人可咋办？”

“（&&（*￥@￥#￥&，小小书生，可懂得了否？”

“老哥，稳！”

（具体如何解，请听下回分解。）

Round 2

后来这个小书生回忆到，老哥解题的过程，可谓是虾几8优化，扣细节啊！缺少的不是天马行空的想法而是扣细节的心！

我们还是直接把2n+1个值进行异或操作，那么最终得到的肯定是A^B嘛！这两个外星人是不是这个世界的人？不是吧，那么他们肯定是卍解操作也即异或之后的结果不为0，既然不为0 的话，把这个值展开成二进制，里面总有某个位置一个为0一个为1，比如你看：
假设：A = 0X01; B = 0X03;
那么A⊕B的值不为0把！展开成二进制细细细细看一下：

0000 0001B
⊕
0000 0011B
-----------
0000 0010B

看到没有异或值不为零的话一定至少在某一位存在一个为1一个为0，如上面的在从右往左数第二位A对应的是0，B对应的是1。

好了，到这里我们知道这两个外星人，噢不，外形狗的异或值在某一位一定存在不一样的值，我们这里找到的是bit1位置（从最右的bit0开始数的），这样子是不是分了两个阵营了？既然阵营都分出来了，然后我们就可以叫大家集合了！

“啊，各位父老乡亲，麻烦大家抬起自己的右脚丫子，从右往左数第二根脚指头指甲盖有分叉的往左站，没分叉的往右站！”

底下一片人头攒动，熙熙攘攘，不出一会人稍安定，人群中就分出了一条道路，稀稀落落地掉着几只鞋子...

“光头队，哦不，天机处烦请进行处理。。。”

在光头对分别对两边进行异或操作之后，每边都最终剩下一个人，没错啦，就是那两个外星人！当然咯，在我们找出第一组的外星人之后，第二组的还需要继续一个个异或找吗？我认为是不需要的，因为我们已经知道A^B的值了，也知道其中一个的值了，那么我们将这两个值再做一次异或那不就是另外一个值咯！

所以在实际写代码的时候，我们可以这样取bit1=1这个特征，然后让所有的值与00000010B进与操作，操作完后不为零则进行异或操作，这样子一轮下来就自动分出两类，且同时其中一个值就出来了，当然了，另外一个外星人也呼之欲出。

“森赛！森赛！请问你为啥就认定这么分类，那些命中人就都会被分在同一阵营呢？”

“小伙子，基础知识不牢靠啊！你想啊，既然是命中人，那么是不是展开成二进制后的所有位都是相同的啊，既然相同，那么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的数字
    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：那要是来了三个外星人呢？
老大哥：你咋不上天呢？

没办法，老大哥为了维持自己的尊严及地位，必须腆着老脸继续掰。

我们取 x = a^b^c，可以获取到的情报是X不为a,b,c中的任意一值。
我们可以反证嘛！假如 x=a，那么x^a = a^a = 0 = a^a^b^c = b^c = 0,而我们的前提条件是啥？！是这三个外形人都是不同的啊！用术语表示就是在这个数组中只出现过一次的数字啊！b^c=0都表示相同了好嘛！其他同理。
由于三个数都是唯一出现的所以x^a = b^c 结果肯定是非零的，其他同理，那么f(x^a)的值也肯定是非零;
我们设定函数f(x)，他的功能是找到自变量x的第一bit位置。我们能得到的情报是f(x^a)、f(x^b)、f(x^c)得到的值肯定都不为0；

我们这里假设:
          X = x^a = b^c
          Y = x^b = a^c
          Z = x^c = a^b
有X^Y^Z = 0，那么就一定有 X、Y、Z 三个数的低位起第一位为1的位置两个相同，一个不同； 比如 ：
X: 00001000
Y: 00000100
Z: 00001100 
Y和Z的低位第一位都是00000100， X的低位第一位是00001000；而且看到没有一定是两个1和一个0哟！而不是两个0和一个1，否则就不会有异或结果为0啦！

我们把X、Y、Z的最低1的位置找出来后，找出那个位置不一样的就是唯一的那个咯！
比如上面的X,找出X的最低位置之后是不是就可以以此位为分类标准，将此位为1的分一类，为0的分一类，
然后将为1的那一类进行异或得到的就是我们要找的外星人啦！这个找到后那么剩下的两个外星人就是上面的找两个问题啦！。

》总结：利用了X^Y^Z = 0则有最低为1的位置具有两个相同一个不同的特性（见上面XYZ的示例），然后就构建出这样的表达式，然后利用一些小trick来实现最终目的，很棒棒！。

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))

结果如下：
c = 2
a = 3, b = 1

“老哥，代码看不懂咋办？”

“小兄弟我都给你转成python版本了，你还看不懂啊？！那我估计，你是被里面的逻辑及写法绕晕了！来我给你捋一捋！”

“啊！咱看代码啊，得讲究个从上而下，先骨架后血肉，跟重构一个复杂信号一样的先把低频信号架起来，然后再贴上一些高频信号补充细节！”

首先你看，从main入口这里显示找到一个外星人，然后再找另外两个外形人，这就是先画出一个整体思路啦！

然后咱们再走进去findoneDogger(array1, len(array1))看看里面是如何实现的：

首先无非是定义一些变量嘛，我们三个外星人的异或值假设为a_XOR_b_XOR_c，先要被找到的外星人命名为c，我们的核心关键信息就是每个数字的第一个出现1的位置啊，那我们就定义为firstonebit就好了！变量都对应初始化为0，为啥是0呢？因为0跟任何数进行异或还是那个数啊！也就是0是纯净的！

第一步干啥呢？还是跟原先一样把所有的值进行异或操作，得到的值肯定是a^bc啊！（注意哟，这里就算是为0，也是可以把这三个外星小崽子找出来的！为0是啥意思呢？为0就是说找了一圈发现一点异常也没有，跟没人来过一样！毕竟我们是根据全部异或来获取线索的嘛！）

第二步来了，这一步我们要干的是分别找出a^b,b^c,c^a的最低一位位置，然后将这三个值进行异或来确定三个组合中哪个属于异类！

到这里就有点麻烦了！我们怎么得到这三个组合的最低位置呢？

我们分析下哈，我们已知的是a^b^c，但是这并没有什么暖用啊！比如说最低位为1的位置找出来也没啥用啊！这是三个数了！不是非此即彼的关系了！
还记得之前的论述的三个数异或为0就有某种特性吗？

不记得没关系！我再给你啰嗦一遍：
假如存在 X^Y^Z = 0，那么一定存在其中两个数的最低1位置是相同的，而剩下那个的最低位是不同的！
你看假如存在：
X:00000100
Y:00000110
Z:00000010
这三个数是不是异或完之后结果为0！而且你发现没有，从低位起往左数，第一个出现1的位置，必须是两个1一起出现，否则是不存在全部异或结果为0的！这就是一个核心的特征啊！
从这里又突然联想到，机器学习是人为地找特征来分类，实际上使用的是人的脑力！而深度学习却是动用强大的计算机算力结合一个算法框架来找到最合适的特征，我们人为找出的解决方案很有可能只是局部最优解而不是全局最优解，而深度学习却是尽力去寻找那个全局最优的，深度学习的目的是找到那个能描述你的特征来尽可能地认出你来！！！

现在我们要做的就是把这个特性给利用起来，令M=a^b^c,那么就有：(M^a)^(M^b)^(M^c) = (b^c)^(a^c)^(a^b) = 0这样子是不是就构建出来了三个变量的异或值为零了！

设：
X = M^a
Y = M^b
Z = M^c

具体代码中如何实现呢？我们最终要的就是X = (b^c)、Y = (a^c)、Z = (a^b)三个值的第一个位置！我们不是可以得到a^b^c的值嘛！这是一个定值M嘛！我拿这个定值跟所有的值都异或一次并取最低位，那么我们就可以得到两个阵营，下图中的左右两个阵营：原本成对的数在异或M之后的值还是一样的嘛！取低位当然还是一样了！左边这个大圈里面就是了，有n对；而那三个外星人与M异或之后取低位肯定会出现两个1位置一样，而剩余一个不一样，大概就如右边这个小框内的数字一样！

好了现在我们把这些值全部异或一下，最后得到的是不是就是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值依次对之进行异或操作并取低位，低位为bit4的作为一组，然后将这组的值进行异或那么得到岂不就是其中一个外星人咯！！！完美！

 for i in range(length):
        if getfirstonebit(a_XOR_b_XOR_c ^ array[i]) == firstonebit:
            c ^= array[i]

剩下的就是找找两个外星人的套路了！easy，顺便说下，之前还考虑到假如a^b^c = 0怎么办？因为总的一轮异或下来结果是0啊，说明完全正常啊！虽然我知道不正常但是却没有一点点线索的感觉！实际上无论是否为0我们都能利用这个隐含条件完美地找出了外星人！只能说，人类的智慧真的是太无穷无尽了！只要你敢想、敢用心！