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

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

交換次數(shù)決定了排序完成時(shí)正確的數(shù)據(jù)寫入到了哪塊內(nèi)存中。

當(dāng)交換次數(shù)為偶數(shù)時(shí)，寫入原內(nèi)存。

當(dāng)交換次數(shù)為奇數(shù)時(shí)，寫入臨時(shí)內(nèi)存。

如果交換次數(shù)為奇數(shù)，那么還要將數(shù)據(jù)拷貝至原內(nèi)存。不過，在兩兩交換時(shí)，不需要額外的內(nèi)存，因?yàn)楸容^數(shù)據(jù)只有一個(gè)，簡(jiǎn)單交換就行了，奇數(shù)次時(shí)先進(jìn)行一次比較，接下來就仍然是偶數(shù)次的了。因此在算法的主要部分前面才有了這段代碼。

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); 
} 

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

事實(shí)上我們只在乎長(zhǎng)度數(shù)量的***1位在哪，因?yàn)槟且晃徊艣Q定交換次數(shù)。

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

很遺憾的是，關(guān)于此問題，目前最快解也只有l(wèi)ogN，基于二分查找法。但是把N降為logN，對(duì)于數(shù)位長(zhǎng)度來說，真有點(diǎn)小題大做，仍然還是想找一個(gè)O(1)的方法才有意義。

之所以有這種想法，因?yàn)樵谖徊僮鞯氖澜缋?，有些算法很是銷魂。

比如 

x&(x-1) 

可將X最右邊起的連續(xù)的0填充為1

x&(-x)

可單獨(dú)抽出最右邊的1

等等。

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

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

不過對(duì)我們的應(yīng)用來說，這還沒到頭，因?yàn)樽罱K的目的是要知道該位是在奇數(shù)位上還是在偶數(shù)位上。因此問題轉(zhuǎn)換為：

把數(shù)組長(zhǎng)度-1，如果最左邊的1落在偶數(shù)位上，則需要偶數(shù)次交換，如果落在奇數(shù)位上則需要奇數(shù)次交換

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

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可以稱為偶數(shù)柵，0x555...55可以稱為奇數(shù)柵，如果***位在偶數(shù)位上，偶數(shù) 柵相與的結(jié)果肯定大于和奇數(shù) 柵相與的結(jié)果的，反之亦是同理，此問題得解。

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