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

想象两个正整数A和b，我想把这两个组合成一个整数C。

不可能有其他整数D和E组合成C。所以把它们和加法运算符结合是不行的。例:30 + 10 = 40 = 40 + 0 = 39 + 1 连接也不管用。例如“31”+“2”= 312 =“3”+“12”

这种组合操作也应该是确定的(总是用相同的输入产生相同的结果)，并且应该总是在整数的正侧或负侧产生一个整数。

当前回答

我们可以在O(1)空间和O(N)时间内将两个数字编码为1。假设您希望将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)

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

2020-11-15 18:00:18

其他回答

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

下面是一个无序配对函数: < x, y > = x * y + trunc ((x - y | | - 1) ^ 2 / 4) = < y、x > 对于x≠y，这里有一个唯一的无序配对函数: <x, y> = if x < y: X * (y - 1) + trunc((y - X - 2)²/ 4) 如果x > y: (x - 1) * y + trunc((x - y - 2)^2 / 4) = <y, x>

2014-03-10 07:00:51

如果你想要更多的控制，比如为第一个数字分配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在这篇文章中的回答。利用这些资源，我可以找出更先进的解决方案

2020-03-02 12:10:53

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将彼此接近的数字映射到它们(与其他方法相比)。

我不明白您所说的:

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

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

2009-05-28 09:24:47

我们可以在O(1)空间和O(N)时间内将两个数字编码为1。假设您希望将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

通过推广，我们得到