http://blog.leezhong.com/tech/2011/06/03/php-xor-find-num.html

給你1-1000個(gè)連續(xù)自然數(shù)，然后從中隨機(jī)去掉兩個(gè)，再打亂順序，要求只遍歷一次，求出被去掉的兩個(gè)數(shù)。

這題其實(shí)挺為面試者的，因?yàn)橐?分鐘內(nèi)說出解法，且不能使用計(jì)算機(jī)、紙和筆。如果之前沒有遇到過類似的題目，加上面試時(shí)的緊張心情，很難能在那么短的時(shí)間里想到解決方案，至少我做不到。

好在我有時(shí)間，上網(wǎng)看了一下，比較常見的有兩種方法

求方程組的解

遍歷被打亂的數(shù)組時(shí)，計(jì)算value的累加值和value平方的累加值。結(jié)合未打亂之前的數(shù)組，這樣就能得出x+y = m與x*x+y*y = n兩個(gè)方程，解這組方程即可算出被去掉的兩個(gè)數(shù)。這種方法比較容易理解，實(shí)現(xiàn)起來也比較簡單

使用異或

這個(gè)就麻煩點(diǎn)了。先來說說異或的定義：兩個(gè)二進(jìn)制位不同的取1。再來說說異或的兩個(gè)特性：順序無關(guān) / 對一個(gè)數(shù)異或兩次等于沒有異或。順序無關(guān)就是說異或的元素可以隨意交換順序，而不會影響結(jié)果。異或兩次可以理解為+x和-x。

計(jì)算出x^y的值

首先，這兩個(gè)數(shù)組(打亂前和打亂后)各自異或，也就是1^2^…^1000，得到兩個(gè)異或值。再對這兩個(gè)異或值進(jìn)行一次異或，這樣就得到了x^y的指(重復(fù)部分互相抵消了)。

// 其實(shí)就是把數(shù)組的所有元素進(jìn)行異或，重復(fù)部分互相抵消 result = 1^2^...^1000^1^2...^1000; result = 1^1^2^2...^x...^y...^1000^1000; result = x^y;

獲取計(jì)算出的異或值的1所在的位置，并繼續(xù)異或

因?yàn)閤和y是兩個(gè)不同的整數(shù)，所以這兩個(gè)數(shù)的異或結(jié)果，轉(zhuǎn)化為二進(jìn)制的話，一定在某位是1，假設(shè)在第3位。也就是說如果把原始數(shù)組按第3位是否為0進(jìn)行劃分，就可以分成兩個(gè)數(shù)組，每個(gè)數(shù)組各包含一個(gè)被抽取的數(shù)。如果打亂后的數(shù)組也按這個(gè)規(guī)則劃分為兩個(gè)數(shù)組，這樣就得到了4個(gè)數(shù)組，其中兩組是第3位為0，另外兩組是第3位為1。把第3位為0的兩個(gè)數(shù)組所有元素進(jìn)行異或就能得到被抽取的一個(gè)數(shù)，同理也就能獲得另外一個(gè)被抽取的數(shù)，于是問題解決。

總結(jié)

以上是生活随笔為你收集整理的异或的妙用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。