原題

一個(gè)整數(shù)，可以表示為二進(jìn)制的形式，請(qǐng)給出盡可能多的方法對(duì)二進(jìn)制進(jìn)行逆序操作。 例如：10000110 11011000的逆序?yàn)?00011011 01100001

分析

題目中說是一個(gè)整數(shù)，對(duì)它的二進(jìn)制進(jìn)行逆序。并不是一個(gè)01字符串，或者01的數(shù)組。那么我們?cè)撊绾谓鉀Q這個(gè)問題呢？方法還是比較多的，有的中規(guī)中矩、有的非常巧妙。我們要掌握中規(guī)中規(guī)的方法，見識(shí)更多的巧妙的方法。慢慢的，能夠舉一反三，在遇到新的問題時(shí)，能夠有靈思妙想。

最直接的方法

直接的方法，很容易想到：有如下代碼：

通過查表的方法

在遇到位操作的問題時(shí)，往往題目中限定了總的位數(shù)，比如這個(gè)題目，我們可以認(rèn)為32位。這就給我們帶來了一個(gè)以空間換時(shí)間的解決思路：查表法。位數(shù)是固定的，可以申請(qǐng)空間，存儲(chǔ)預(yù)先計(jì)算好的結(jié)果，在計(jì)算其他的結(jié)果的時(shí)候，則查表即可。

32位相對(duì)于查表來講，還是太大了。既然這樣縮小范圍，32個(gè)bit，也就是4個(gè)byte。每個(gè)byte 8bit，可以表示0-255的整數(shù)?？梢酝ㄟ^申請(qǐng)256大小的數(shù)組，保存這256個(gè)整數(shù)，二進(jìn)制逆序之后的整數(shù)。然后將一個(gè)32位的整數(shù)，劃分為4個(gè)byte，每一個(gè)byte查表得到逆序的整數(shù)：r1,r2,r3,r4。按照r4r3r2r1順序拼接二進(jìn)制得到的結(jié)果就是最終的答案。

這是一個(gè)思路，大家可以進(jìn)一步思考，嘗試。

巧妙的方法

我們這里主要分析這個(gè)巧妙的方法，核心思想是：分治法。即：

•逆序32位分解為兩個(gè)逆序16位的
•逆序16位分解為兩個(gè)逆序8位的
•逆序8位分解為兩個(gè)逆序4位的
•逆序4位分解為兩個(gè)逆序2位的
最后一個(gè)2位的逆序，直接交換即可。也就是分治遞歸的終止條件。但是，在上面的過程中，還沒有應(yīng)用到位操作的技巧。根據(jù)動(dòng)態(tài)規(guī)劃的思想，我們可以自底向上的解決這個(gè)問題：

•每2位為一組，進(jìn)行交換，完成2位逆序
•每4位為一組，前面2位與后面2位交換，完成4位逆序
•每8位為一組，前面4位和后面4為交換，完成8位的逆序
•每16位為一組，前面8位和后面8位交換，完成16位的逆序
2組16位的交換，完成32位的逆序

通過下面的例子，詳解上面的過程，我們以16位為例：10000110 11011000

經(jīng)過4步，逆序完成。推而廣之，總的時(shí)間復(fù)雜度為O(logn)，n是二進(jìn)制的位數(shù)。這個(gè)方法可以推廣到任意位。

示例代碼如下：

int v =111;
v =((v >>1)&0x55555555)|((v &0x55555555)<<1);
v =((v >>2)&0x33333333)|((v &0x33333333)<<2);
v =((v >>4)&0x0F0F0F0F)|((v &0x0F0F0F0F)<<4);
v =((v >>8)&0x00FF00FF)|((v &0x00FF00FF)<<8);
v =( v >>16)|( v <<16);System.out.println(v);上面的思路理解了，代碼不難理解。例如第二行，前邊是取偶數(shù)位，后面是取奇數(shù)位，奇數(shù)位左移一位，偶數(shù)位右移一位，再取或，就是交換了奇數(shù)偶數(shù)位。也就是第一個(gè)步驟。

基于位運(yùn)算的一些巧妙的方法有很多。大家可以自行研究，后面會(huì)和大家分享更多的面試題目。

【分析完畢】

最新評(píng)論