将两个整数映射到一个整数（带有上限）

Question

我正在寻找一个函数，将两个（正）整数映射到一个新的整数中，该新整数可以被反转为原始组合。 这个问题以前已经被问过，例如 Mapping two integers to one, in a unique and deterministic way。不同之处在于其中一个整数受到相当小的上限约束，例如50。另一个整数没有限制。

我试图解决的问题是，我有1-50个数组，其中包含1-max int（但大多数<10.000.000）的数字。

array1 {1,2,3,4,5,6,7..N)  
array2 {1,2,3,4,5,6,7..N)  
array50 {1,2,3,4,5,6,7..N)  

现在我想创建一个单一的新数组，将这些N个数组组合成一个新数组，其中每个数字都可以反转到原始数组。因此，我考虑创建一对数字，一个指向数组，一个指向数组中的实际数字。

如果我使用默认函数如Cantor Pairing Function，很快就会得到巨大的数字，我试图尽可能保持这些数字尽可能小。最好的情况是最大部分只适合Int32而不是long。我认为这应该是可能的，因为我的一对数字中的一个数字被50限制，但我想不出如何做到这一点。

- Joeri

---

只有在两者都有界限的情况下才能明确执行，因为int是有界限的。 - harold

我得到非常快的大数字 - 比BigInteger还要大吗？ - Sinatr

是的，两者都有界限。但一个界限在1-50之间，另一个界限在1-MaxInt之间。@Sinatr：如果你使用康托对偶函数，例如100000,4，你会得到5000450014。这个方法是可行的，但当达到200000时，已经超出了int32的范围（20000900014）。 - Joeri

问题是1..MaxInt需要31位，而1..50只需要6位，而(31+6)>32，所以在32位中无法同时存储这两个数字。 - Matthew Watson

如果你需要6位来表示1到50之间的数字，那么较大的数字将被限制在26位内，范围为0到67,108,863。 - Matthew Watson

Answer 1

如果你有两个数字

• a 从0到a_max - 1
• b 从0到2³²/a_max - 1

你可以将它们组合为

x = a + a_max*b;

而且组合数x将适应32位无符号整数。

要解码它们，请使用

a = x%a_max;
b = x/a_max;

---

^{找不到更有效的打包方式，因为每个可能的输出值都被使用了。（输出中没有“间隙”）如果b的边界太窄，必须使用更大的输出类型。}

- alain

---

但是原帖中a_max的值为2^31，这意味着b的范围应该是从0到1，但他希望b的范围是从1到50。 - Matthew Watson

是的，b也必须有界限，否则没有更大的类型是不可能的。但看起来OP可能会接受一个边界。 - alain

谢谢。看起来很简单，但它确实做到了我想要的功能。 - Joeri