c++ - C++ 编译器是否识别 2 的幂？

Question

我正在构建一个自定义散列，其中我根据公式对字符串中的所有字母求和:

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++ 编写时它确实会移位 数量 *= 2;但只是为了澄清一下，对吗？

---

谢谢，我找到了如何在调试器中查看 dissassembly。是的，如果您像这样使用它，编译器会理解移位

number *= 65536

但是，如果你这样做，它会进行正常的乘法运算

number1 = 65536
number *= number1;

Answer 1

试试吧!

你用的是什么编译器？您可以告诉大多数编译器在编译后将中间文件留在原地，或者只编译(而不是汇编)，这样您就可以实际查看它生成的汇编代码。

你可以在这个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) 开始乘数。循环的每次迭代，我将乘数向右旋转一位。这实际上是将它除以二，直到得到 1，之后它变成 0x80000000。