2

次のような方法で入力をスクランブルする必要があるユースケースがあります。

  1. 各特定の入力は、常に特定の疑似ランダム出力にマップされます。
  2. 増分入力が疑似ランダム出力にマップされるように、出力は入力を十分にシャッフルする必要があります。

たとえば、入力が64ビットの場合、正確に2 ^ 64の一意の出力が必要であり、これらは可能な限り増分入力を中断する必要があります（任意の要件）。

これをC＃でコーディングしますが、SIMD組み込み関数がない限り、JavaまたはCから変換できます。私が探しているのは、車輪の再発明ではなく、既存のコードです。

Googleを調べましたが、1：1のマッピングを行うものは見つかりませんでした。

4

2 に答える 2

1

頭のてっぺんから：

  1. 入力をシフトします。すべてのビットを保持するようにしてください。つまり、2 つのシフト操作を異なる方向に使用し、結果を OR します。

  2. 静的 XOR を適用します。

私の頭に浮かぶ他のすべては、全単射ではありません。ただし、全単射を検索すると、何か役に立つものが出てくるかもしれません;D

于 2012-09-11T13:11:34.687 に答える
1

これはかなりうまくいくようです：

const long multiplier = 6364136223846793005;
const long mulinv_multiplier = -4568919932995229531;
const long offset = 1442695040888963407;

static long Forward(long x)
{
    return x * multiplier + offset;
}

static long Reverse(long x)
{
    return (x - offset) * mulinv_multiplier;
}

multiplier定数は、奇数でmulinv_multiplierモジュラー乗法逆数 ( wiki:モジュラー乗法逆数または Hackers Delight 10-15 Exact Division by Constants を参照) multiplier(モジュロ 2^64 を参照) である限り、何にでも変更できmultiplierます。奇数でなければ、逆数はありません)。

オフセットは何でもかまいませんが、安全のために 2^64 で比較的素数にしてください。

これらの特定の定数は、Knuths 線形合同ジェネレーターから取得されます。

小さなことが 1 つあります。入力の LSB の補数を結果の LSB に入れます。それが問題になる場合は、ゼロ以外の量だけ回転させることができます。

32 ビットの場合、定数はmultiplier = 0x4c957f2d、offset = 0xf767814f、mulinv_multiplier = 0x329e28a5です。

64 ビットの場合はmultiplier = 12790229573962758597、 のmulinv_multiplier = 16500474117902441741方がうまくいく場合があります。

または、CRC64 の場合、この用途に可逆な(つまり、入力が CRC と同じサイズである) CRC を使用することもできますが、もちろんいくつかの変更が必要です。

于 2012-09-11T13:36:07.440 に答える