奇妙的異或運算

在數字邏輯中，邏輯異或(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