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

Cantor pairing function 考虑到其简单、快速和节省空间,它确实是其中一个更好的,但Wolfram发表了一些更好的东西 by Matthew Szudzik, here Cantor配对函数的局限性(相对而言)是编码结果的范围并不总是保持在 2N 如果输入为2,则为位整数 N 位整数。也就是说,如果我的输入是2 16 位整数范围为 0 to 2^16 -1 ,那么有 2^16 * (2^16 -1) 输入的组合是可能的,所以显而易见 Pigeonhole Principle 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

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

康托尔配对函数 :

两个最大16位有符号整数(3276732767)的映射将是2147418112,刚好小于有符号32位整数的最大值。

现在 Szudzik函数 :

(3276732767)=>;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 对于输入并遍历函数,然后将输出除以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;
}

由于中间计算可能超过以下限制 二倍体 有符号整数,我用过 4N 整数类型(最后除以 2. 将结果带回 二倍体

我提供的关于替代解决方案的链接很好地描绘了利用空间中每个点的函数图。

你在找一个双射词 NxN -> N 地图。这些用于例如。 dovetailing 请看 this PDF 介绍所谓 维基百科引入了一个特定的配对功能,即 Cantor pairing function :

三点意见:

• 正如其他人所表明的那样,如果你计划实现一个配对函数,你可能很快就会发现你需要任意大的整数(bignum)。
• 如果你不想区分配对(a,b)和(b,a),那么在应用配对函数之前,先对a和b进行排序。
• 实际上,我撒了谎。你正在寻找一个双射词 ZxZ -> N 地图。Cantor函数只对非负数有效。然而,这不是问题,因为定义双射很容易 f : Z -> N ,就像这样:
• f(n)=n*2 如果n>;= 0
• f(n)=-n*2-1 如果n<;0

如果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,或者如果你加,则从上半部分减去1。

铸造 (unsigned)A 避免在将窄类型默认提升为签名后的左移中出现签名溢出UB int 对于更广泛的类型,避免转移你要保留的部分也很重要,比如 ((uint64_t)A << 32 | B ,因为默认促销停止在 整数 .

这 (unsigned)B 演员阵容不是必需的;重要的是,它 unsigned short B 首先。左手边 | 存在 unsigned 意味着这也将转换为 无符号 .

您可以将其与签名类型一起使用,至少是getA和getB,并且可以返回签名类型 整数 从 combine ,但是输入需要零扩展,所以在C中你需要它们 无符号短整型 在扩大之前。喜欢 ((unsigned)(unsigned short)A << 16) | (unsigned short)B

您可能想使用 uint16_t 和 uint32_t ,定义类型宽度以匹配您正在使用的班次计数。

这有可能吗?
您正在组合两个整数。它们的范围都是-2147483648到2147483647,但你只会得到肯定的结果。 这使得2147483647^2=461169E+18个组合。 由于每个组合都必须是唯一的,并且结果是一个整数,因此您需要某种可以包含如此数量的数字的神奇整数。

还是我的逻辑有缺陷?

让号码 a b 第二个。让 p 成为 a+1 -第素数, q 成为 b+1 -第素数

那么,结果是 pq ,如果 a<b, 或 2pq 如果 a>b .如果 a=b ,随它去吧 p^2 .

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

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

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

你可以修改这个来处理负面 x 和 y

例如

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

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

#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更通用的方法更有效。它的解码也相当简单;对于初学者来说,不需要平方根:)

1. 这是一个 unordered pairing function :

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

2. 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>
   

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 .
• 它返回的值非常小——如果你打算将其用于数组索引,这很好,因为数组不必很大。
• 它是缓存友好的——如果两个(a,b)对彼此接近,那么f会将数字映射到彼此接近的(与其他方法相比)。

我不明白你的意思:

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

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

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

检查这个: 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的值有点困难。

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

A=B+C*N

哪里

B=A%N=B

C=A/N=C

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

假设是32位整数,则有2147483647个正整数。在顺序无关紧要且重复的情况下选择其中两个,得到2305843008139952128个组合。这不适合32位整数集。

但是,您可以将此映射调整为61位。使用64位整数可能是最简单的。将高位字设置为较小的整数,低位字设置为较大的整数。

更简单的方法怎么样:给定两个数字,A和B让str是连接:'A'+';B然后让输出为hash(str)。我知道这不是一个数学答案,但一个简单的python(内置哈希函数)脚本应该能完成这项工作。

假设你有一个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位) 要获取编号a:

int a = nums_mapper.GetNumA(bnum);

要获取num b:

int b = nums_mapper.GetNumB(bnum);

编辑: 二进制数 可以存储在类中。我这样做不是因为我自己的需要 我分享了代码,希望它会有所帮助。

感谢来源: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ mouviciel 在这篇文章中回答。 使用这些资源,我可以找到更高级的解决方案

我们可以在O(1)空间和O(N)时间中将两个数字编码为一个。

  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)

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

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

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

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

缺点:结果的大小是一个问题。但没关系,为什么我们无论如何都要在计算机中存储无界整数。

将以下两个非负整数合并 你可以简单地将它们的数字交织成一个。

示例: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。(这在编程中可能不是很有用,除非你使用定点数。)

请注意,我们如何利用前导零在整数部分不重要的优势,就像尾随零在小数部分不重要一样。