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

小开

如果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会将上面的位设置为全1或，或者如果你添加，则从上半部分减去1。

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

(unsigned)B类型转换不是必需的;重要的部分是它开始时是unsigned short B。|的左边为unsigned意味着它也将转换为unsigned。

你可以对有符号类型使用这个，至少是getA和getB，并且你可以从combine返回有符号的int，但是输入需要0 -extend，所以在C语言中，你需要它们在扩展之前是unsigned short。像((unsigned)(unsigned short)A << 16) | (unsigned short)B

你可能想要使用uint16_t和uint32_t来定义类型宽度，以匹配你正在使用的移位计数。

小开

设数字a为第一个，b为第二个。设p为__abc3素数，q为__abc5素数

然后，如果a<b,，结果为pq;如果a>b，结果为2pq。如果a=b，则设为p^2。

小开

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

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

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

你可以修改它来处理负x和y，方法是用5和7的幂来编码标志。

如。

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

小开

最佳答案

你正在寻找一个双射NxN -> N映射。它们用于例如燕尾榫接合。看一下这个PDF关于所谓的配对函数的介绍。Wikipedia介绍了一个特定的配对函数，即康托配对函数:

pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2

备注:三个

其他人已经明确指出，如果计划实现配对函数，可能很快就会发现需要任意大的整数(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

小开

这可能吗? 两个整数的组合。它们都有- 2147,483,648到2147,483,647的范围，但你只会看到正数。 2147483647^2 = 4,61169e +18种组合。因为每个组合都必须是唯一的，并且结果是一个整数，所以您需要某种神奇的整数来包含这个数量的数字。

还是我的逻辑有问题?

小开

你的建议是不可能的。总会有碰撞。

为了将两个对象映射到另一个单独的集合，映射的集合必须具有预期组合数量的最小大小:

假设有一个32位整数，则有2147483647个正整数。选择其中两个顺序无关紧要且具有重复的组合，将得到2305843008139952128个组合。这并不适合32位整数的集合。

不过，你可以把这个映射压缩成61位。使用64位整数可能是最简单的。将高的字设置为较小的整数，低的字设置为较大的整数。

小开

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 & lt;> < /代码。李< / >
它返回非常小的值——如果你打算用它来做数组索引，那很好，因为数组不需要很大。
它是缓存友好的——如果两个(a, b)对彼此接近，那么f将彼此接近的数字映射到它们(与其他方法相比)。

我不明白您所说的:

总是在上产生一个整数不管是积极的还是消极的整数的边

我如何在这个论坛写(大于)，(小于)字符?

小开

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

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

小开

构造一个映射并不难:

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的值有点难。

小开

尽管Stephan202的答案是唯一真正通用的答案，但对于有限范围内的整数，您可以做得更好。例如，如果你的范围是0..1万，那么你可以这样做:

#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更通用的方法效率稍高。它的解码也简单得多;对于初学者来说，不需要平方根:)

小开

康托配对函数确实是其中一个更好的，因为它简单，快速和空间高效，但还有一些更好的东西在Wolfram 作者:Matthew Szudzik发布。康托配对函数(相对而言)的限制是，如果输入是两个N位整数，则编码结果的范围并不总是停留在2N位整数的限制内。也就是说，如果我的输入是两个从0 to 2^16 -1开始的16位整数，那么可能有2^16 * (2^16 -1)的输入组合，因此通过明显的N0，我们需要一个至少为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) to 2^15 -1开始的signed 16位整数(稍后我们将看到如何扩展输出以跨越有符号范围)。因为a和b必须是正的，所以它们的范围从0 to 2^15 - 1开始。

康托配对函数:

两个最大最多的16位有符号整数(32767,32767)的映射将是2147418112，这恰好小于32位有符号整数的最大值。

现在Szudzik的功能:

(32767, 32767) => 1073741823, many small ..

让我们考虑负整数。我知道这超出了最初的问题，但只是详细说明，以帮助未来的游客。

康托配对函数:

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。64位输出的16位输入可能是如此不可原谅!!

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's，你可以这样做:

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位整数的限制范围内，这很酷。我不确定如何对康托配对函数进行同样的处理，但没有尝试那么多，因为它不那么有效。此外，康托配对函数涉及的计算量更多，也意味着它的速度更慢。

下面是一个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)。

我提供的替代解决方案的链接很好地描绘了利用空间中的每一个点的函数图。令人惊讶的是，你可以将一对坐标可逆地唯一编码为一个数字!神奇的数字世界!!

小开

对于作为参数的正整数和参数顺序无关的情况:

下面是无序配对函数:

<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>

For x ≠ y, here's a unique unordered pairing function:

<x, y> = if x < y:
x * (y - 1) + trunc((y - x - 2)^2 / 4)
if x > y:
(x - 1) * y + trunc((x - y - 2)^2 / 4)
= <y, x>

小开

假设我们有两个数字B和C，把它们编码成一个数字A

A = b + c * n

在哪里

B= a % n = B

C= a / n = C

小开

下面是基于@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

小开

再简单一点:给定两个数字，A和B让str为串联:'A' + ';' + 'B'。然后让输出为hash(str)。我知道这不是一个数学答案，但一个简单的python(有一个内置的哈希函数)脚本应该做这项工作。

小开

给定正整数A和B，设D = A的位数，E= B的位数结果可以是D, 0, E, 0, a，和b的串联

示例:A = 300, B = 12。D = 3, E=2 result = 302030012。这利用了一个事实，即唯一以0开头的数字是0，

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

缺点:结果的大小是个问题。不过没关系，我们为什么要在电脑里存储无界整数呢。

小开

假设你有一个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

小开

如果你想要更多的控制，比如为第一个数字分配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位) 得到num a:

int a = nums_mapper.GetNumA(bnum);

要得到num b:

int b = nums_mapper.GetNumB(bnum);

编辑: bnum可以存储在类中。我做这件事不是因为我自己的需要我分享了代码，希望对大家有所帮助感谢来源: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ 函数提取位，也感谢这篇文章中的mouviciel答案。使用这些资源，我可以找到更高级的解决方案

小开

我们可以在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)

你可以通过除法和对结果取余来得到每个数字。