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

我有一个用例，其中我需要以以下方式加扰输入：


每个特定的输入始终映射到特定的伪随机输出。
输出必须充分混洗输入，以便递增的输入映射到伪随机输出。


例如，如果输入为64位，则必须确切地有2 ^ 64个唯一输出，并且这些输出必须尽可能破坏增量输入（任意要求）。

我将使用C＃进行编码，但是只要没有SIMD内在函数，就可以从Java或C进行翻译。我正在寻找的是一些已经存在的代码，而不是重新发明轮子。

我看过Google，但是没有找到可以进行1：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是multiplier的模乘乘法逆（请参见wiki:modular multiplicative inverse或Hackers Delight 10-15精确除以常数），就可以将常数更改为任何值（模2 ^ 64，显然-这就是为什么multiplier必须为奇数，否则它没有反数的原因。

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

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

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



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

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



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