以唯一和确定的方式将两个整数映射为一个

Question

以唯一和确定的方式将两个整数映射为一个假设两个正整数A和B，我想把这两个正整数组合成一个整数C。不可能有其他的整数D和E组合到C，所以把它们和加法运算符结合起来就不起作用了。例如：30+10=40=40+0=39+1也不起作用。“31”+“2”=312=“3”+“12”这种组合操作也应该是确定性的(总是用相同的输入产生相同的结果)。和应该总是在整数的正反两面产生一个整数。

Answer 1

Cantor配对函数考虑到它的简单、快速和空间效率，它确实是最好的之一，但是在Wolfram上有一些更好的出版。马修·斯祖德齐克著..Cantor配对函数(相对的)的限制是编码结果的范围并不总是停留在2N如果输入为两个比特整数N位整数。也就是说，如果我的输入是两个16位整数0 to 2^16 -1，然后2^16 * (2^16 -1)输入的组合是可能的，所以很明显针孔原理，我们至少需要一个大小的输出。2^16 * (2^16 -1)，等于2^32 - 2^16的地图32在理想情况下，位数应该是可行的。在编程世界中，这可能并不是没有实际意义的。

Cantor配对函数:

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

两个最大的16位整数(65535，65535)的映射将是8589803520，正如您所看到的，这不能适合32位。

进入Szudzik函数:

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

现在(65535，65535)的映射将是4294967295，正如您所看到的，这是一个32位(0到2^32-1)整数。这就是这个解决方案理想的地方，它只是利用了空间中的每一个点，所以没有什么能获得更高的空间效率。

---

现在，考虑到我们通常在语言/框架中处理不同大小的数字签名实现，让我们考虑signed 16位整数-(2^15) to 2^15 -1(稍后我们将看到如何将输出扩展到跨越签名范围)。自a和b必须是积极的，他们的范围从0 to 2^15 - 1.

Cantor配对函数:

两个最大16位有符号整数(32767，32767)的映射将是2147418112，这只是缺少有符号32位整数的最大值。

现在Szudzik函数:

(32767，32767)=>1073741823，小得多。

让我们来解释一下负整数。这超出了我所知道的最初的问题，但只是为了帮助未来的访客。

Cantor配对函数:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768，-32768)=>8589803520，即64。16位输入的64位输出可能是不可原谅的！

Szudzik函数:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768，-32768)=>4294967295，对于无符号范围是32位，对于有符号范围是64位，但是更好。

现在，所有这些都是积极的。在签名世界里，如果我们能把一半的输出转移到负轴，就会节省更多的空间。..你可以这样为Szudzik：

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

我所做的：在计算重量之后2对于输入，并通过函数，然后将输出除以2，然后将其中的一部分乘成负轴。-1.

有关签名范围内的任何输入，请参见结果。16位数，输出在有符号的范围内。32位整数，很酷。我不知道如何对Cantor配对功能进行相同的方式，但没有尝试，因为它没有那么有效。此外，Cantor配对函数所涉及的更多的计算也意味着它的速度也较慢。.

这里是一个C#实现。

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

因为中间计算可以超过2N有符号整数，我使用了4N整数类型(最后一次除以2把结果带回2N).

我在交替解决方案上提供的链接很好地描述了利用空间中的每一个点的函数的图表。令人惊奇的是，您可以唯一地将一对坐标编码为单个数字，可以可逆地进行编码！神奇的数字世界！

Answer 2

如果A和B可以用2个字节表示，则可以在4个字节上组合它们。把A放在最重要的一半，B放在最不重要的一半。

在C语言中，这给出了(假设size of(Short)=2和size of(Int)=4)：

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}