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

Question

我有一个用例，我需要以这样的方式对输入进行加扰：

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

例如，如果输入是 64 位，则必须恰好有 2^64 个唯一输出，并且这些输出必须尽可能地中断递增输入（任意要求）。

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

我在谷歌上看过，但没有找到任何可以进行 1:1 映射的东西。

Answer 1

只是从我的头顶：

1. 移位输入：确保保留每一位，即在不同方向上使用两个移位操作并将结果组合在一起。

2. 应用静态 XOR。

我想到的其他一切都不是双射的。但是，搜索双射可能会带来一些有用的东西；D

Answer 2

这似乎工作得很好：

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 线性同余生成器。

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

---

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

对于 64 位，multiplier = 12790229573962758597,mulinv_multiplier = 16500474117902441741可能会更好。

---

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