3

我正在构建一个自定义哈希，我根据公式将字符串中的所有字母相加：

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; 编写时它确实会移位。但只是为了澄清，是吗？

谢谢，我发现了如何在调试器中查看反汇编。是的，如果您像这样使用编译器，编译器确实知道移位

number *= 65536

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

number1 = 65536
number *= number1;
4

6 回答 6

5

尝试一下！

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

你可以在我的另一个问题上看到这正是我所做的。

例如，在 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 具有按位旋转指令（ror分别rol用于向右和向左旋转）。但是，C 没有提供表达旋转操作的方法。所以我定义了ROR为你旋转的宏。（理解它的工作原理留给读者作为练习！）

在我的循环中，我像您一样在 0x10000 (65536) 处开始乘法器。循环的每次迭代，我将乘数向右旋转一位。这实际上将它除以 2，直到达到 1，然后它变为 0x80000000。

于 2012-12-18T13:53:11.103 回答
3

答案取决于您的编译器、硬件架构以及可能的其他因素。

用移位代替这种乘法是最好的做法，这甚至不是先验的。我认为通常应该让编译器进行指令级优化。

也就是说，让我们看看我的编译器做了什么:)

int i, j;

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

使用gcc 4.7.2with编译的-O3结果是

_main:
LFB0:
        movq    _i@GOTPCREL(%rip), %rax
        movl    (%rax), %edx
        movq    _j@GOTPCREL(%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-18T13:54:58.833 回答
2

为什么不直接使用 C++ 中内置的移位运算符？

(string[0] << 16) + (string[1] << 15) + (string[2] << 14) + ...
于 2012-12-18T14:12:07.240 回答
2

您可以使用模板元编程，它确保在编译时计算 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-18T14:12:25.270 回答
1

您可以通过不断地乘以 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-18T14:20:06.337 回答
0

没有规则；编译器将生成将给出正确结果的代码。当这是最快的解决方案时，我知道的所有编译器都会使用移位和加减的组合。我曾在整数乘法比移位快的系统上工作过。我还在一个系统上工作，其中编译器生成的代码比 for更好，尽管机器没有硬件乘法。h * 127(h << 7) - h

如果您希望将数字作为 const 数组的初始值设定项，那么显而易见的答案是使用其他程序生成它们，然后插入生成的文本。

于 2012-12-18T14:03:24.920 回答