C++編譯器是否能識別2的冪次？

我建立一個自定義的哈希在那裏我根據公式總結在字符串中的所有字母：C++編譯器是否能識別2的冪次？

string[0] * 65536 + string[1] * 32768 + string[2] * 16384 + ...

而且我已經來到了一個問題，我是否應該在int數組定義爲常量這樣，這些數字：

const int MULTIPLICATION[] = { 
    65536, 
    32768, 
    16384, 
    8192, 
    4096, 
    2048, 
    1024, 
    512, 
    256, 
    128, 
    64, 
    32, 
    16, 
    8, 
    4, 
    2, 
    1 
}

或者，也許我應該只生成這些數據而計算哈希值本身（而可能失去由於他們一些速度沒有被已經產生的）？我需要計算該哈希數百萬次，我想編譯器來了解主要的是，而不是正常的MUL操作

MOV EBX, 8 
MUL EBX

它會做

SHL EAX, 3

編譯器不明白，如果我乘以2的冪來移位而不是通常的乘法？

另一個問題，我敢肯定，它確實移位時，你寫在C++ number * = 2; 但只是爲了澄清，是嗎？

謝謝，我已經找到了如何在調試器中查看dissasembly。是的，編譯器也明白，如果你使用它像

number *= 65536

但是轉移位，它只是做普通的乘法，如果你做

number1 = 65536 
number *= number1;

來源

2012-12-18 Vanilla Face

通過熟悉調試器，您可以找到這些問題的答案。用它來打破你想知道的代碼，然後檢查當時的拆卸。 :) –

你爲什麼不問你的編譯器？ –

沒有固定的答案，「編譯器會用shift來代替乘法」;這取決於您使用的編譯器，體系結構和可能的編譯器標誌。 – mah

試試吧！

你使用什麼編譯器？你可以告訴大多數編譯器在編譯之後將中間文件放在適當的位置，或者只是編譯（而不是彙編），所以你可以看看它生成的彙編代碼。

你可以在other question of mine上看到，這正是我所做的。

例如，在gcc中-S標誌表示「僅編譯」。並且-masm=intel生成更易讀的組件，IMO。

編輯

這一切都表示，我認爲以下是你正在尋找（未經測試）算法：

// Rotate right by n bits 
#define ROR(a, n) ((a >> n) | (a << (sizeof(a)*8-n))) 


int custom_hash(const char* str, int len) { 
    int hash = 0; 
    int mult = 0x10000; // 65536, but more obvious 

    for (int i=0; i<len; i++) { 
     hash += str[i] * mult; 
     mult = ROR(mult, 1);  
    } 

    return mult; 
}

首先，你沒有指定當你有超過16個字符時會發生什麼（什麼是乘法器？）所以在這個實現中，我使用了一個按位旋轉。 x86有bitwise rotate instructions（分別爲左右旋轉的ror和rol）。但是，C沒有提供表達旋轉操作的方法。所以我定義了爲您旋轉的ROR宏。（瞭解它是如何工作的，僅供讀者參考！）

在我的循環中，我像你一樣在0x10000（65536）處啓動乘法器。循環的每次迭代，我將乘數右移一位。這基本上將它除以2，直到你達到1，之後它變成0x80000000。

來源

2012-12-18 13:53:11

我正在使用VC2010，我會尋找您所說的選項。 –

@VanillaFace在VC++中，選項是'/ Fa'，後面跟着一個可選的文件名（沒有空格）。在Visual Studio中，在源文件的屬性中，在C/C++ →輸出文件中，有一個用於彙編器輸出和ASM列表位置的條目。 –

答案取決於你的編譯器，硬件架構和其他可能的東西。

先驗甚至不明顯，用換檔替代這種乘法是最佳的選擇。我認爲通常應該讓編譯器進行指令級優化。

那麼，讓我們看看我的編譯器:)

int i, j; 

int main() { 
    j = i * 8; 
}

此，使用gcc 4.7.2與-O3編譯，結果在

_main: 
LFB0: 
     movq [email protected](%rip), %rax 
     movl (%rax), %edx 
     movq [email protected](%rip), %rax 
     sall $3, %edx     ;<<<<<<<<<< THE SHIFT INSTRUCTION 
     movl %edx, (%rax) 
     ret

所以，在我的環境，答案顯然是「是」。

至於你的其他問題，不要預先計算MULTIPLICATION。要獲得係數

string[0] * 65536 + string[1] * 32768 + string[2] * 16384 + ...

剛開始coeff = 65536，並轉向一個位向右每次迭代：

coeff >>= 1;

來源

2012-12-18 13:54:58 NPE

假設你使用相同的編譯器，有很多C++編譯器，*你的*恰好是這樣做的，另一個可能不是。 –

@HunterMcMillen：當然。請參閱我的（更新）答案的第一句。 – NPE

如果你讓我'char'，那就會發現可能令人驚訝的'movsbl'（我的意思是結果可能會令人驚訝;編譯器做到這一點並不奇怪。） – rici

有沒有規則;編譯器將生成代碼，這會給以正確的結果。我知道的所有編譯器將使用組合移位和加減當即最快的解決方案。我已經在整數乘法比換檔更快的系統上工作;我也在編譯器爲h * 127生成了比(h << 7) - h更好的代碼的系統上工作，儘管事實上這個機器沒有硬件乘法。

如果您希望數字作爲常量數組的初始值設定，當然，課程的顯而易見的答案是使用其他一些程序生成它們，並插入生成的文本。

來源

2012-12-18 14:03:24

爲什麼不使用內建於C++的移位運算符？

(string[0] << 16) + (string[1] << 15) + (string[2] << 14) + ...

來源

2012-12-18 14:12:07

我仍然是C++ noob :( 但是，一旦我看到它，暗示了<<運算符在我的程序中。 –

+1這應該是最直接的解決方法。 – iammilind

可以使用模板元編程，這確保了2的冪是在編譯時計算出，而不管編譯的：

template<unsigned int SHIFT> 
struct PowerOf2 
{ 
    static const size_t value = 1 << SHIFT; 
};

爲了便於使用宏如下：

#define CONSTRUCT(I) (string[I] * PowerOf2<16 - I>::value)

正在使用，

CONSTRUCT(0)

等同於：

string[0] * 65536

來源

2012-12-18 14:12:25 iammilind

不錯，我會在將來明確檢查這個！ –

您可以通過2乘以不斷積累它。

int doubleRunningTotalAndAdd(int runningTotal, unsigned char c) 
{ 
    runningTotal *= 2; 
    runningTotal += c; 
    return runningTotal; 
} 

string s = "hello"; 

int total = accumulate(s.rbegin(), s.rend(), 0, doubleRunningTotalAndAdd);

來源

2012-12-18 14:20:06

C++編譯器是否能識別2的冪次？

回答

相關問題