以一种独特且确定性的方式将两个整数映射为一个

Question

想象两个正整数 A 和 B。我想将这两个组合成一个整数 C。

不能有其他整数 D 和 E 组合成 C。 因此将它们与加法运算符结合起来是行不通的。 例如 30 + 10 = 40 = 40 + 0 = 39 + 1 连接也不起作用。 例如“31”+“2”= 312 =“3”+“12”

此组合运算也应该是确定性的（使用相同的输入始终产生相同的结果）并且应该始终产生一个整数整数的正数或负数。

Answer 1

Cantor 配对函数 考虑到其简单、快速且节省空间，它确实是最好的函数之一，但是，Wolfram Matthew Szudzik 在此处发表了一些更好的内容。 康托配对函数（相对）的局限性在于，如果输入是两个 N 位，则编码结果的范围并不总是保持在 2N 位整数的限制内整数。 也就是说，如果我的输入是两个 16 位整数，范围从 0 到 2^16 -1，则有 2^16 * (2^16 - 1) 输入可能的组合，因此根据明显的鸽洞原理，我们需要一个输出大小至少为 2^16 * (2^16 -1)，等于 2^32 - 2^16，或者换句话说，一个地图理想情况下，32 位数字应该是可行的。 这在编程世界中可能具有不小的实际重要性。

康托尔配对函数：

(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）整数。 这就是该解决方案的理想之处，它只是利用该空间中的每个点，因此没有什么可以提高空间效率。

---

现在考虑到我们通常在语言/框架中处理不同大小的数字的有符号实现，让我们考虑范围从 -(2^15) 到 2^15 的有符号 16 位整数-1（稍后我们将看到如何扩展输出以跨越有符号范围）。 由于 a 和 b 必须为正数，因此它们的范围为 0 到 2^15 - 1。

康托尔配对函数：

两个最大 16 位有符号整数 (32767, 32767) 的映射将为 2147418112，这刚好低于有符号 32 位整数的最大值。

现在Szudzik 的函数：

(32767, 32767) => 1073741823，小得多..

让我们考虑负整数。 这超出了我知道的最初问题，但只是为了帮助未来的访客而详细阐述。

康托尔配对函数：

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 这是 Int64。 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 权重并遍历该函数后，我将输出除以二，并将其中一些取负数轴乘以 -1。

查看结果，对于有符号 16 位数字范围内的任何输入，输出都在有符号 32 位整数的限制内，这很酷。 我不确定如何以相同的方式实现康托配对功能，但没有尝试太多，因为它效率不高。 此外，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

您正在寻找双射 NxN -> N 映射。 这些用于例如吻合。 请查看此 PDF，了解所谓的配对功能。 维基百科介绍了一个特定的配对函数，即 Cantor 配对函数：

三点注释：

• 正如其他人已经明确指出的，如果您打算实现配对函数，您可能很快就会发现您需要任意大的整数（bignums）。
• 如果您不想区分 (a, b) 和 (b, a) 对，请在应用配对函数之前对 a 和 b 进行排序。
• 其实我撒谎了。 您正在寻找双射 ZxZ -> N 映射。 康托尔函数仅适用于非负数。 但这不是问题，因为定义双射很容易 f : Z -> N，如下所示：
• f(n) = n * 2 if n >= 0
• f(n) = -n * 2 - 1 if n < 0

Answer 3

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

在 C 语言中，这给出（假设 sizeof(short)=2 和 sizeof(int)=4）：

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

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

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

使输入 unsigned Short 或 uint16_t 确保它们在之前进行零扩展您将 | 或 + 它们放在一起。 否则，负数 B 会通过 OR 将高位设置为全 1，或者如果进行 ADD，则从上半部分减一。

在默认将窄类型提升为有符号 int 后，强制转换 (unsigned)A 可以避免左移中的有符号溢出 UB。 对于更广泛的类型，避免移出要保留的位也很重要，例如 ((uint64_t)A << 32 | B，因为默认提升在 int 处停止

(unsigned)B 转换不是必需的；重要的是它是 unsigned Short B 的左侧。 >| 是 unsigned 意味着这也将转换为 unsigned

您可以将其与有符号类型一起使用，至少是 getA 和 getB，并且您可以返回有符号。来自 combine 的 int，但输入需要零扩展，因此在 C 中，您需要在加宽之前将它们设置为 unsigned Short。 ((unsigned)(unsigned short)A << 16) | (unsigned short)B

您可能需要使用 uint16_t 和 uint32_t 来定义类型宽度与您正在使用的班次计数相匹配。

Answer 4

这可能吗？
您正在组合两个整数。 它们的范围都是 -2,147,483,648 到 2,147,483,647，但您只能取正数。
这使得 2147483647^2 = 4,61169E+18 个组合。
由于每个组合都必须是唯一的并且结果是一个整数，因此您需要某种可以包含这么多数字的神奇整数。

还是我的逻辑有问题？

Answer 5

正整数的标准数学方法是利用素因数分解的唯一性。

f( x, y ) -> 2^x * 3^y

缺点是图像往往跨越相当大的整数范围，因此当涉及到用计算机算法表达映射时，您可能会在为结果选择合适的类型时遇到问题。

您可以修改它，通过对具有 5 和 7 项的幂的标志进行编码来处理负 x 和 y。

例如

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Answer 6

设数字 a 为第一个，b 为第二个。 令 p 为第 a+1 个素数，q 为第 b+1 个素数

那么，如果a，结果为pq，如果a>b，结果为2pq。 如果a=b，则设为p^2。

Answer 7

尽管 Stephan202 的答案是唯一真正通用的答案，但对于有界范围内的整数，您可以做得更好。 例如，如果您的范围是 0..10,000，那么您可以执行以下操作：

#define RANGE_MIN 0
#define RANGE_MAX 10000

unsigned int merge(unsigned int x, unsigned int y)
{
    return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}

void split(unsigned int v, unsigned int &x, unsigned int &y)
{
    x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
    y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}

结果可以适合范围最大为整数类型基数平方根的单个整数。 这种打包方式比 Stephan202 更通用的方法稍微高效一些。 解码起来也相当简单； 对于初学者来说不需要平方根:)

Answer 8

对于正整数作为参数且参数顺序无关紧要：

1. 这是一个 无序配对函数：

   ;   = x * y + trunc((|x - y| - 1)^2 / 4) =  
     

2. 对于 x ≠ y，这里有一个 独特的无序配对功能：

   ;   = 如果 x <   y: 
                x * (y - 1) + trunc((y - x - 2)^2 / 4) 
              如果x>   y: 
                (x - 1) * y + 截断((x - y - 2)^2 / 4) 
            =  
     

Answer 9

f(a, b) = s(a+b) + a，其中 s(n) = n*(n+1)/2

• 这是一个函数 - - 它是确定性的。
• 它也是单射的——f 为不同的 (a,b) 对映射不同的值。 你可以证明
  这是使用以下事实： s(a+b+1)-s(a+b) = a+b+1
  < 一个。
• 它返回非常小的值——如果您打算将它用于数组索引，那么这很好，因为数组不必很大。
• 它是缓存友好的——如果两个 (a, b) 对彼此接近，则 f 将数字映射到彼此接近的它们（与其他方法相比）。

我不明白你的意思：

应该总是产生一个整数
无论是积极的还是消极的
整数的一边

如何在这个论坛中写（大于）、（小于）字符？

Answer 10

这是基于 @nawfal 给出的方法将 @DoctorJ 的代码扩展到无界整数。 它可以编码和解码。 它适用于普通数组和 numpy 数组。

#!/usr/bin/env python
from numbers import Integral    

def tuple_to_int(tup):
    """:Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
    if len(tup) == 0:  # normally do if not tup, but doesn't work with np
        raise ValueError('Cannot encode empty tuple')
    if len(tup) == 1:
        x = tup[0]
        if not isinstance(x, Integral):
            raise ValueError('Can only encode integers')
        return x
    elif len(tup) == 2:
        # print("len=2")
        x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2])  # Just to validate x and y

        X = 2 * x if x >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < Y):
            return Z // 2
        # Map odds onto negative
        else:
            return (-Z - 1) // 2
    else:
        return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:]))  # ***speed up tuple(tup[2:])?***


def int_to_tuple(num, size=2):
    """:Return: the unique tuple of length `size` that encodes to `num`."""
    if not isinstance(num, Integral):
        raise ValueError('Can only encode integers (got {})'.format(num))
    if not isinstance(size, Integral) or size < 1:
        raise ValueError('Tuple is the wrong size ({})'.format(size))
    if size == 1:
        return (num,)
    elif size == 2:

        # Mapping onto positive integers
        Z = -2 * num - 1 if num < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < s:
            X, Y = Z - s * s, s
        else:
            X, Y = s, Z - s * s - s

        # Undoing mappint to positive integers
        x = (X + 1) // -2 if X % 2 else X // 2  # True if X not divisible by 2
        y = (Y + 1) // -2 if Y % 2 else Y // 2  # True if Y not divisible by 2

        return x, y

    else:
        x, y = int_to_tuple(num, 2)
        return int_to_tuple(x, size - 1) + (y,)


def isqrt(n):
    """":Return: the largest integer x for which x * x does not exceed n."""
    # Newton's method, via http://stackoverflow.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

Answer 11

检查一下：http://en.wikipedia.org/wiki/Pigeonhole_principle。 如果A、B、C是同一类型，则不能这样做。 如果A和B是16位整数，而C是32位整数，那么你可以简单地使用移位。

哈希算法的本质是它们无法为每个不同的输入提供唯一的哈希值。

Answer 12

构建映射并不难：

   1  2  3  4  5  use this mapping if (a,b) != (b,a)
1  0  1  3  6 10
2  2  4  7 11 16
3  5  8 12 17 23
4  9 13 18 24 31
5 14 19 25 32 40

   1  2  3  4  5 use this mapping if (a,b) == (b,a) (mirror)
1  0  1  2  4  6
2  1  3  5  7 10
3  2  5  8 11 14
4  4  8 11 15 19
5  6 10 14 19 24


    0  1 -1  2 -2 use this if you need negative/positive
 0  0  1  2  4  6
 1  1  3  5  7 10
-1  2  5  8 11 14
 2  4  8 11 15 19
-2  6 10 14 19 24

弄清楚如何获取任意 a、b 的值要困难一些。

Answer 13

让我们有两个数字 B 和 C ，将它们编码为单个数字 A

A = B + C * N

其中

B=A % N = B

C=A / N = C

Answer 14

你的建议是不可能的。 你们总会有冲突。

为了将两个对象映射到另一个集合，映射集合的最小大小必须达到预期的组合数量：

假设是 32 位整数，则有 2147483647 个正整数。 选择其中两个（顺序无关紧要且重复）会产生 2305843008139952128 个组合。 这不太适合 32 位整数集合。

不过，您可以将此映射装入 61 位。 使用 64 位整数可能是最简单的。 将高位字设置为较小的整数，将低位字设置为较大的整数。

Answer 15

更简单的事情怎么样：给定两个数字，A 和 B 让 str 成为串联：'A' + ';' +“B”。 然后让输出为hash(str)。 我知道这不是一个数学答案，但一个简单的 python（有一个内置的哈希函数）脚本应该可以完成这项工作。

Answer 16

假设您有一个 32 位整数，为什么不将 A 移至前 16 位一半，将 B 移至另一半呢？

def vec_pack(vec):
    return vec[0] + vec[1] * 65536;


def vec_unpack(number):
    return [number % 65536, number // 65536];

除了尽可能节省空间和计算成本之外，一个非常酷的副作用是您可以对打包的数字进行向量数学运算。

a = vec_pack([2,4])
b = vec_pack([1,2])

print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Scalar multiplication

Answer 17

如果您想要更多控制，例如为第一个数字分配 X 位，为第二个数字分配 Y 位，您可以使用以下代码：

class NumsCombiner
{

    int num_a_bits_size;
    int num_b_bits_size;

    int BitsExtract(int number, int k, int p)
    {
        return (((1 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << num_a_bits_size) | num_a;
    }

    int GetNumA(int bnum)
    {
        return BitsExtract(bnum, num_a_bits_size, 1);
    }

    int GetNumB(int bnum)
    {
        return BitsExtract(bnum, num_b_bits_size, num_a_bits_size + 1);
    }
};

我总共使用 32 位。 这里的想法是，例如，如果您希望第一个数字最多为 10 位，第二个数字最多为 12 位，您可以这样做：

NumsCombiner nums_mapper(10/*bits for first number*/, 12/*bits for second number*/);

现在您可以在 num_a 中存储最大数字即 2^10 - 1 = 1023，在 num_b 中，最大值为 2^12 - 1 = 4095。

设置 num A 和 num B 的值：

int bnum = nums_mapper.StoreAB(10/*value for a*/, 12 /*value from b*/);

现在 bnum 是所有位（总共 32 位。您可以修改代码以使用 64 位）
获取数字 a：

int a = nums_mapper.GetNumA(bnum);

获取数字 b：

int b = nums_mapper.GetNumB(bnum);

编辑：
bnum 可以存储在类内部。 我不是因为我自己的需要才这么做的
我分享了代码，希望对您有所帮助。

感谢您提供来源：
https://www.geeksforgeeks.org/extract-k-bits -给定位置编号/
用于提取位的函数，也感谢本文中的 mouviciel 回答。
使用这些资源我可以找出更高级的解决方案

Answer 18

我们可以在 O(1) 空间和 O(N) 时间内将两个数字编码为一个。
假设您要将 0-9 范围内的数字编码为 1，例如： 5、6.怎么做？ 很简单，

  5*10 + 6 = 56. 
   
    5 can be obtained by doing 56/10 
    6 can be obtained by doing 56%10.

即使对于两位整数，比如 56 和 45，56*100 + 45 = 5645。我们可以通过执行 5645/100 和 5645%100 再次获得单个数字，

但是对于大小为 n 的数组，例如： a = {4,0,2,1,3}，假设我们要对 3 和 4 进行编码，因此：

 3 * 5 + 4 = 19               OR         3 + 5 * 4 = 23
 3 :- 19 / 5 = 3                         3 :- 23 % 5 = 3
 4 :- 19 % 5 = 4                         4 :- 23 / 5 = 4

推广后，我们得到

    x * n + y     OR       x + n * y

但是我们还需要注意我们更改的值； 所以它最终是

    (x%n)*n + y  OR x + n*(y%n)

你可以通过除法并找到结果数字的模来单独获得每个数字。

Answer 19

对于新手，我想通过指出以下参考文献（那里的公式 2.1）来补充 @nawfal 的精彩答案：

The Rosenberg-Strong Pairing Function

数学公式如下：给定 a, b 两个非负整数，我们感兴趣的是函数 f，使得 f(a, b) = f(a', b') == > a=a'，b=b'。

上述参考文献提供了 Rosenberg-Strong 函数 $f$ 定义如下：

f(a, b) = (max(a,b))^2 + max(a, b) + a - b

这看起来比 Cantor 的更经济和 Szudzik 的（查看参考文献中的图 2 以了解编码的工作原理！枚举看起来是最佳的）。

请注意，Szudzik 撰写了这篇论文，但并未将他自己的优雅解决方案放入本文中。

Answer 20

给定正整数 A 和 B，令 D = A 的位数，E = B 的位数
结果可以是 D、0、E、0、A 和 B 的串联。

示例：A = 300，B = 12。D = 3，E=2 结果 = 302030012。
这利用了唯一以 0 开头的数字是 0 的事实，

优点：易于编码，易于解码，人类可读，可以首先比较有效数字，无需计算即可进行比较的潜力，简单的错误检查。

缺点：结果的大小是一个问题。 但这没关系，为什么我们要在计算机中存储无界整数呢？

Answer 21

要将两个任意大小的非负整数合并为一个，只需将它们的数字交错即可。

示例：12345 和 678：

1 2 3 4 5
     6 7 8
----------
1020364758

结果是 1020364758。

您可以使用任何基数（例如基数 2 或基数 16）执行此操作。 结果最多是最大数字的两倍，这意味着例如组合两个 16 位数字将始终适合 32 位。

如果我们还想允许负整数，我们可以通过将绝对值乘以 2 来编码其中之一或两者，然后如果数字为负则加 1。 解码时，模 2 将表示符号。

我们可以将此方法扩展到小数，例如，如果我们想要组合 1234.5 和 6.78：

1 2 3 4 .5
       6. 7 8
-------- ----
10203046.5708

结果是 10203046.5708。 （这在编程中可能不是很有用，除非您使用定点数。）

请注意我们如何利用整数部分中的前导零无关紧要，就像小数部分中的尾随零无关紧要一样。