c# - 高效的位重映射算法

Question

我有一个用例，我需要以这样的方式加扰输入:

1. 每个特定的输入总是映射到一个特定的伪随机输出。
2. 输出必须充分混洗输入，以便递增输入映射到伪随机输出。

例如，如果输入是 64 位，则必须恰好有 2^64 个唯一输出，并且这些输出必须尽可能打破递增输入(任意要求)。

我将使用 C# 编写此代码，但可以从 Java 或 C 转换，只要没有 SIMD 内在函数。我正在寻找的是一些已经存在的代码，而不是重新发明轮子。

我在 Google 上看过，但没有找到任何可以进行 1:1 映射的内容。

Answer 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:modular multiplicative inverse 或 Hackers Delight 10-15 Exact Division by Constants ) 的 multiplier(模 2^64，显然 - 这就是为什么 multiplier 必须是奇数，否则它没有逆)。

偏移量可以是任何值，但为了安全起见，将其与 2^64 相对质数化。

这些特定常数来自 Knuth 的线性同余生成器。

有一件小事:它将输入的 LSB 的补码放在结果的 LSB 中。如果这是一个问题，您可以将其旋转任何非零量。

---

对于 32 位，常量可以是 multiplier = 0x4c957f2d，offset = 0xf767814f，mulinv_multiplier = 0x329e28a5。

对于 64 位，multiplier = 12790229573962758597，mulinv_multiplier = 16500474117902441741 可能效果更好。

---

或者，您可以使用 CRC，对于 CRC64，它是 reversible(即输入与 CRC 的大小相同)，当然需要进行一些修改。