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) から開始します。ループの反復ごとに、乗数を 1 ビット右に回転させます。これは基本的に、1 になるまで 2 で割り、その後は 0x80000000 になります。

于 2012-12-18T13:53:11.103 に答える
3

答えは、コンパイラ、ハードウェア アーキテクチャ、および場合によってはその他のものによって異なります。

そのような乗算をシフトに置き換えることが最善の方法であることは、先験的に明らかではありません。一般的には、命令レベルの最適化をコンパイラーに任せるべきだと思います。

そうは言っても、私のコンパイラが何をするか見てみましょう:)

int i, j;

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

gcc 4.7.2これをwithを使用してコンパイルすると-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、反復ごとに右に1ビットシフトします。

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

ルールはありません。コンパイラは、正しい結果を与えるコードを生成します。私が知っているすべてのコンパイラーは、それが最速の解決策である場合、シフトと加算および減算の組み合わせを使用します。私は整数の乗算がシフトよりも速いシステムに取り組んできました。また、マシンにハードウェア乗算がなかったにもかかわらず、コンパイラがよりも優れたコードを生成するシステムにも取り組んできました。h * 127(h << 7) - h

もちろん、const配列の初期化子として数値が必要な場合、明らかな答えは、他のプログラムで数値を生成し、生成されたテキストを挿入することです。

于 2012-12-18T14:03:24.920 に答える