右移位與兩除之差（size_t）

這是從Linux內核3.12.1中取得的二進制搜索算法。因爲size_t總是>=0，我想知道爲什麼我們不能用>>替換/2？右移位與兩除之差（size_t）

/** 
* @key: pointer to item being searched for 
* @base: pointer to first element to search 
* @num: number of elements 
* @size: size of each element 
* @cmp: pointer to comparison function 
*/ 
void *bsearch(const void *key, const void *base, size_t num, size_t size, 
     int (*cmp)(const void *key, const void *elt)) 
{ 
    size_t start = 0, end = num; 
    int result; 

    while (start < end) 
    { 
     size_t mid = start + (end - start)/2; 

     result = cmp(key, base + mid * size); 
     if (result < 0) 
      end = mid; 
     else if (result > 0) 
      start = mid + 1; 
     else 
      return (void *) base + mid * size; 
    } 
    return NULL; 
}

來源

2013-11-24 user2767553

我們爲什麼要更換它？對人類或電腦有任何好處嗎？ – delnan

我想任何體面的編譯器都會將此表達式優化爲最有效的形式。 – Crozin

爲什麼我們不應該用純機器碼重寫內核？當然，我們可以比任何愚蠢的編譯器做得更好。 –

因爲這是不成熟的優化 - 最有可能的編譯器足夠聰明來實現，並且將兩個改變劃分成一個單一的右移。

來源

2013-11-24 12:43:36

您只需要提供它沒有的編譯器信息。編譯器已經知道size_t是一個無符號類型，所以它可以編譯/ 2就好像它已經是>> 1一樣。任何現代編譯器都會進行這種轉換

有時，程序員有編譯器沒有的信息。它可以是這樣的：

/* requires y to be larger than x */ 
int f(int x, int y) { 
    int z = y - x; 
    return z/2; 
}

在上面的函數，編譯器不能變換劃分成一個簡單的移位（儘管它可以轉化成一種使用移位和避免了除法更長的序列）。在這種情況下，您可以考慮編寫>> 1而不是/ 2。但是當信息可以從程序中推斷出來時，讓編譯器推斷它。如果您注意到，在閱讀生成的程序集時（您應該一直在做這件事：它可以節省您對此問題的麻煩），考慮到易於獲得的信息生成了次優代碼，並提交了改進請求您的編譯器的開發人員，而不是使您的源代碼不易讀。

來源

2013-11-24 14:28:51

右移位與兩除之差（size_t）

回答

相關問題