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)，您就可以将常量更改为任意值)的乘数(显然，模2^64 - 这就是为什么乘数必须是奇数，否则它没有逆数)。

偏移量可以是任何值，但为了安全起见，请使其相对素数 2^64。

这些特定常数来自 Knuths 线性同余发生器。

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

---

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

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

---

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