c - 20 ビットの入力を 5 ビットの出力に圧縮するハッシュ関数

Question

20 ビット長の入力を取り、出力の長さは 5 ビットのみにするハッシュ関数のアルゴリズムを考え出す必要があります。

先週インターネットで検索しましたが、役立つものは何も見つかりませんでした。

あなたの助けは非常に高く評価されています. ありがとう

Answer 1

簡単な解決策は、入力を 5 ビットの 4 つのブロックに分割し、それらを XOR することです。

Answer 2

この計算は、Barmar によって提案されているように、「入力を 5 ビットの 4 つのブロックに分割し、それらを XOR する」ことと同等ですが、おそらく少し効率的です (x入力はどこにありますか)。

t = x ^ (x>>10);
result = (t ^ (t>>5)) & 31;

ただし、XOR アプローチは、一般に、元の 20 ビットを攪拌して混合することはありません。一部のマシンでは、このアプローチはクロッカーのアプローチよりも高速であり、他のマシンではその逆です。

Answer 3

:edit: オリジナルまたは新しいアルゴリズムが本当に必要ですか? （つまり、これは学校の課題です）。

標準ライブラリの乱数ジェネレーターを使用して、20 ビットをシードすることができます。使用するアルゴリズムは十分すぎるほどです。C の rand() に使用される一般的なアルゴリズムは?

標準実装の 1 つを選択するだけで問題ありません。以下の例は、野生 (非ポータブル側) に住んでいるだけです。rand の実装はコンパイラまたはライブラリのバージョンによって異なるため、ハッシュを使用する場合、それらを普遍的なものに使用する場合は一致しませんが、実行時のメッセージ チェックサムが必要なだけであるか、学校の課題であると確信しています。 .

#include <time.h>
#include <stdlib.h>
...
int compress20To5(int input) {
    srand( input );
    return rand() & 0x1f; // mask last 5 bits 0x1f (11111b)
}