奇妙的异或运算

在数字逻辑中，逻辑异或(Exclusive or)是一种二元逻辑加法运算操作类型，其操作对象是两个运算元(素)，结果是无进位的第三元。异或运算操作对简单的运算元0与1若两两数值相同时结果为0，数值不同时为1。对于其他十进制数值的异或运算操作，则需先将其转化为一定长度的二进制数值，对两运算元相同位数上的0或1作异或运算操作。这种看似简单的异或运算操作可以解决一些复杂的智力问题，下面介绍一例。

 

囚犯A和B被告知，他们可以提前释放，只要他们能解决警卫在8X8方格棋盘上随机选择一个方格的谜题。在该8X8方格中，每一块方格可以只有一个硬币或者是空格。守卫隔离A，并在棋盘上仅向B展示一个他随机选择的方格，要求B在棋盘上的某个方格中只添加或移除一枚硬币作为对A的提示，尔后A不与B交流，仅通过观察棋盘上硬币的分布辩别守卫向B显示的特定方格。如果A能通过棋盘上硬币的分布分辨出守卫选择的方格，A和B都可以释放。在警卫向B展示棋盘之前，A和B知道要采取的规则和步骤，并被允许设置游戏策略，即构建算法来解决谜题。

 

例如下图是有14枚硬币在棋盘上的一个分布，其中x表示该方格占有硬币，显示红圈的为守卫选择的方格(一般情况下该方格硬币可有可无)。囚犯B需要在棋盘某一方格中添加(如果为空)或取下(如果己占)硬币，用以提示A守卫所选择带红圈的方格。哪个方格需要添加或取出硬币？为方便起见，可以假定在方格中取出硬币等价于在该方格上添加第二枚硬币，问题则为囚犯B在采取某种策略的前提下，应该在哪一个方格里添加一枚硬币可以正确地提示囚犯A关于守卫在棋盘上所选择的方格？

囚犯A和B可以约定对棋盘上硬币标号进行异或运算操作。棋盘上每一方格可以用数字0－63标号，故每一枚硬币所处的方格可以唯一地用0－63中一个数字表示出来。B进一步对所有硬币所占方格的标号以及守卫选择的方格进行异或运算，结果就是囚犯B需要添加一枚硬币方格的标号，注意棋盘方格标号是随机但是唯一的。假定所有硬币标号在异或操作后结果为a，守卫所选方格标号为b，c = (a异或b)则为需要添加硬币方格的标号。因此A仅需对其后所有硬币方格的标号进行异或运算，其结果就是守卫选择的方格标号。

 

证明十分简单。我们知道，任意a与b对于异或运算，(a异或b)=(b异或a)，(a异或a) = (b异或b) = 0，故上述(c异或c)=((a异或b)异或c)=(a异或c异或b)= ((a异或c)异或b)=0，从而(a异或c)= b。

 

由此可见，在囚犯B选择方格标号c放置一枚硬币后，囚犯A可以将他所观察的硬币通过事先约定的方格标号，将所有硬币的标号作异或操作，得出守卫所选择的方格。这里我们无需考虑取出硬币(等价于同一方格两枚硬币)的情况，因为有两枚硬币同一标号的异或运算等价于0。

 

在上例中，如果我们先自左向右然后从上到下将棋盘方格顺序标号，则所有硬币方格标号异或操作后为十进制数49，守卫所选方格为21，(49异或21)=36，当囚犯添加一枚硬币于标号36(注意这里是取出或添加第二枚硬币)的方格后，(49异或36)=21。

 

参见http://datagenetics.com/blog/december12014/index.html

 

所有跟帖： 

• 为啥搞那么复杂？ -avw- ♀ (0 bytes) () 10/07/2023 postreply 09:22:06

• 孩子quant面试好像遇到过这个问题，解题要用到algebraic operation “Exclusive or”。 -BeLe- ♀ (0 bytes) () 10/07/2023 postreply 09:40:56

• 你太厉害了。连孩子的面试题都知道。 -小松松- ♀ (0 bytes) () 10/07/2023 postreply 09:45:08

• 孩子面试后都会做笔记记录下来。 -BeLe- ♀ (0 bytes) () 10/07/2023 postreply 09:50:38

• 晕，娃还记笔记，爹还看 -怀旧一点点- ♀ (77 bytes) () 10/07/2023 postreply 10:22:23

• 娃会拿给你看吗? -zaocha2002- ♀ (0 bytes) () 10/07/2023 postreply 10:39:43