關於位操作的幾個小智力題

01-28

看！大灰機！Σ( ° △ °|||)︴

wow~ (′⊙o⊙)? 看！小灰象！！！

是的，昨天，在平和友好的氣氛中，矮矮胖胖憨態可掬的小飛象同學向我陸陸續續地描述了一個問題。

今天早上我終於想明白了問題應該是什麼樣的。

假設 $f(n)=AND(n,n-1)$ ，其中 $AND(a,b)$ 表示 $a$ 和 $b$ 的二進位表示的逐位與。

給定正整數 $n$ 求使得 $f^m(n)=0$ 的最小正整數 $m$ 。

例如 $f(9999)=9998$ , $f(9998)=9996$ ， $f(9996)=9992$ ， $f(9992)=9984$ ， $f(9984)=9728$ ， $f(9728)=9216$ ， $f(9216)=8192$ ， $f(8192)=0$ ，此時 $m=8$ 。

分析 $n$ 和 $n-1$ 的二進位表示就發現差別從 $n$ 的二進位表示的最右一個「 $1$ 」開始，將「 $10...0$ 」變為「 $01...1$ 」。

於是 $n$ 和 $n-1$ 的逐位與的實際效果就是「將 $n$ 的二進位表示的最右一個「1」變為「0」！

所以 $m$ 就等於 $n$ 的二進位表示中的「1」的個數。

於是這個方法可以用來判斷「正整數 $n$ 是否是 2 的冪?」，只要判斷 $f(n)$ 是否為0即可。

於是就聯想起來看到過的一些和「位」有關的小題目：

? 在一個0-1串 $n$ 中（圖中假設 $n$ 是1個位元組，8個比特)，希望知道右數第 $i$ 個比特是1還是0（從右往左數時從0開始計數）（圖中假設 $i=4$ ）。

解答：

AND(n,1<<i)n

說明：

?在一個0-1串 $n$ 中，希望將右數第 $i$ 個比特設置為1。

解答：

OR(n,1<<i)n

說明：

? 在一個0-1串 $n$ 中，希望將右數第 $i$ 個比特設置為0。

解答：

AND(n,NOT(1<<i))n

說明：

? 給出兩個0-1串 $N$ 和 $M$ ，以及兩個二進位位的位置 $i$ 和 $j$ 。寫一個方法來將 $N$ 中的第 $i$ 到 $j$ 位替換為 $M$ （假設 $M$ 的長度恰好可以填入，結果是 $M$ 是 $N$ 中從第 $i$ 位開始到第 $j$ 位的子串）。

解答：先把 $N$ 中相應位置都設置為「0」，然後對 $M$ 做向左移位，然後逐位或。

? 數組中，只有一個數出現一次，剩下都出現兩次，找出這個出現一次的數。

解答：將所有數都做逐位異或。

說明： $oplus$ 表示異或運算（即模2加法）， $0oplus0=0$ ， $0oplus1=1$ ， $1oplus0=1$ ， $1oplus1=0$ 。異或運算滿足交換律、結合律，且具有一個重要性質 $xoplus x=0$ 。

此外，還有一些規律如 $OR(a,b)+AND(a,b)=a+b$ ， $OR(a,b)-AND(a,b)=aoplus b$ ， $AND(a, b)oplus AND(a, c)=AND(a, (boplus c))$ ， $aoplus AND(a,b)=AND(a, aoplus b)=AND(a,NOT(b))$ ，等等。

事實上，考慮元素數最少的有限域 $mathbb{F}_2$ ，就會發現 $mathbb{F}_2=({0,1},oplus,AND)$ ，也即「與」是其中的乘法，「異或」是其中的加法。
所以交換律、結合律、分配律都是自然的。

? 數組中，只有兩個數出現一次，剩下都出現兩次，找出出現一次的數。

解答：將所有數都做逐位異或。得到結果是這兩個數的異或結果，其中必定有某一位是1。對於原來的數組，根據這個位置是1還是0進行分類。於是這兩個數一定不在同一類，而且每一類都是「只有一個數出現一次，剩下都出現兩次」。

? 給定兩個0-1串 $a$ 和 $b$ ，計算需要改變 $a$ 的多少位才能得到 $b$ 。

解答：數一數 $aoplus b$ 中「1」的個數。

? 假設 $a$ 和 $b$ 都是正整數，證明： $a-bleq aoplus b$ 。

解答：注意到 $a+b=2AND(a,b)+(aoplus b)$ ，而後 $a-b-aoplus b=2(AND(a,b)-b)leq 0$ 。

說明：類似地，可以證明 $a-b+aoplus bgeq0$ 。

（ $a-b+aoplus b=2(OR(a,b)-b)$ ）

? 將 $a$ ， $b$ 兩個數的值進行交換，並且不使用任何的中間變數。

解答： $a = aoplus b$ ， $b = aoplus b$ ， $a = aoplus b$ 。

其中 $oplus$ 表示異或運算（即模2加法）， $0oplus0=0$ ， $0oplus1=1$ ， $1oplus0=1$ ， $1oplus1=0$ 。

註：主要利用了 $xoplus x=0$ 。

? 最後一個問題：假設 $g(n)=OR(n,n+1)$ ，給定正整數 $n$ 求使得 $g^m(n)+1$ 是2的冪的最小正整數 $m$ 。

（解答留給讀者吧）

最後，還是補充幾句吧，網上還有一些據說是筆試題/面試題——例如下面幾個，然而我並不喜歡，就列著玩兒玩兒不分析了。

數組中，只有一個數出現一次，剩下都出現三次，找出出現一次的數。
假設x和y都是整數，得到其中較小的那個。

y^( (x^y)& -(x<y) ) n

將一個int型的數的奇偶位互換，例如6的2進位為0110，第一位與第二位互換，第三位與第四位互換，得到1001，輸出應該為9 。

((n<<1)&(0xAAAA))|((n>>1)&(0x5555)) n

給出兩個正整數a和b, 求他們的和, 但不能使用任何數學運算符。