像這樣簡單的算法前人工程師肯定想到過，即使你是初學者，如果偶然發現了這個也并不稀罕，我也沒有打算效仿郭小四竊他人成果自居，說到底這只是一篇系列扯淡文，它真正有價值的部分是由此延伸出來的問題。

在歸并算法中，合并兩個數列需要消耗m+n的空間，排序好了后還要將隊列拷回。在我的版本的算法中，可一開始就申請一塊等長內存，然后順次的寫入數據，而不需要寫回，一遍寫完后，交換兩塊內存，繼續寫。這樣減少了一半的寫開銷，避免了重復申請空間的問題。

交換次數決定了排序完成時正確的數據寫入到了哪塊內存中。

當交換次數為偶數時，寫入原內存。

當交換次數為奇數時，寫入臨時內存。

如果交換次數為奇數，那么還要將數據拷貝至原內存。不過，在兩兩交換時，不需要額外的內存，因為比較數據只有一個，簡單交換就行了，奇數次時先進行一次比較，接下來就仍然是偶數次的了。因此在算法的主要部分前面才有了這段代碼。

int temp = len,i = 0,size = 1; 
int l1p,l1end,l2p,l2end; 
int *templist,*listb; 
printarr(list,len); 
if(len<=1){ 
    return; 
} 
i = 0; 
//calculate swaptimes 
while(temp){ 
    temp = temp>>1; 
    i++; 
} 
if(i%2){ 
    for(i=0;(i+1)<len;i+=2){ 
        if(list[i]>list[i+1]){ 
            temp = list[i]; 
            list[i] = list[i+1]; 
            list[i+1] = temp; 
        } 
    } 
    size = 2; 
    printarr(list,len); 
} 

這段代碼雖然完成了任務，但是有處地方特么讓人不爽。就是在算交換次數的地方，用了一個O(n)的循環來獲得次數。感覺有點不效率。

事實上我們只在乎長度數量的***1位在哪，因為那一位才決定交換次數。

于是開始尋找有沒有更快的方法。在英文中這個問題叫Find the log base 2 of an integer，這里有一個斯坦福的頁面講這個問題 http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

很遺憾的是，關于此問題，目前最快解也只有logN，基于二分查找法。但是把N降為logN，對于數位長度來說，真有點小題大做，仍然還是想找一個O(1)的方法才有意義。

之所以有這種想法，因為在位操作的世界里，有些算法很是銷魂。

比如 

x&(x-1) 

可將X最右邊起的連續的0填充為1

x&(-x)

可單獨抽出最右邊的1

等等。

所以總是覺得，咱們的問題，也是能用O(1)解決的。

但是這些簡單好用的魔法似乎都只和數的右側沾邊，因為操縱右邊的位數，可以用確切知道的數，比如1 或FFFFFF，而想像操作右邊位一樣操作左邊位就不行了，除非你知道該數的log base 2 interger是什么……如果我們有辦法填充最左邊的0，就能得解，但這個看似很簡單的問題，居然是個至今都無解的題，除非新版cpu出了求專門問題對應的指令，要想在低于logN的步驟內解決這個似乎不可能了。

不過對我們的應用來說，這還沒到頭，因為最終的目的是要知道該位是在奇數位上還是在偶數位上。因此問題轉換為：

把數組長度-1，如果最左邊的1落在偶數位上，則需要偶數次交換，如果落在奇數位上則需要奇數次交換

這樣一來問題似乎很好解決了，這是改寫后的代碼

int temp = len-1,i = 0,size = 1; 
int l1p,l1end,l2p,l2end; 
int *templist,*listb; 
printarr(list,len); 
if(len<=1){ 
    return; 
} 
//calculate swaptimes,only if highest bit in odd place 
if((temp&0xaaaaaaaa)<(temp&0x55555555)){ 
    for(i=0;(i+1)<len;i+=2){ 
        if(list[i]>list[i+1]){ 
            temp = list[i]; 
            list[i] = list[i+1]; 
            list[i+1] = temp; 
        } 
    } 
    size = 2; 
    printarr(list,len); } 

0xAAA...AA可以稱為偶數柵，0x555...55可以稱為奇數柵，如果***位在偶數位上，偶數 柵相與的結果肯定大于和奇數 柵相與的結果的，反之亦是同理，此問題得解。

原文鏈接：http://my.oschina.net/u/1167335/blog/142894