想象两个正整数A和b,我想把这两个组合成一个整数C。
不可能有其他整数D和E组合成C。 所以把它们和加法运算符结合是不行的。例:30 + 10 = 40 = 40 + 0 = 39 + 1 连接也不管用。例如“31”+“2”= 312 =“3”+“12”
这种组合操作也应该是确定的(总是用相同的输入产生相同的结果),并且应该总是在整数的正侧或负侧产生一个整数。
想象两个正整数A和b,我想把这两个组合成一个整数C。
不可能有其他整数D和E组合成C。 所以把它们和加法运算符结合是不行的。例:30 + 10 = 40 = 40 + 0 = 39 + 1 连接也不管用。例如“31”+“2”= 312 =“3”+“12”
这种组合操作也应该是确定的(总是用相同的输入产生相同的结果),并且应该总是在整数的正侧或负侧产生一个整数。
当前回答
你正在寻找一个双射NxN - >n映射。这些是用于例如燕尾。请看这个PDF文件,它介绍了所谓的配对函数。维基百科介绍了一个特定的配对函数,即康托配对函数:
备注:三个
As others have made clear, if you plan to implement a pairing function, you may soon find you need arbitrarily large integers (bignums). If you don't want to make a distinction between the pairs (a, b) and (b, a), then sort a and b before applying the pairing function. Actually I lied. You are looking for a bijective ZxZ -> N mapping. Cantor's function only works on non-negative numbers. This is not a problem however, because it's easy to define a bijection f : Z -> N, like so: f(n) = n * 2 if n >= 0 f(n) = -n * 2 - 1 if n < 0
其他回答
你正在寻找一个双射NxN - >n映射。这些是用于例如燕尾。请看这个PDF文件,它介绍了所谓的配对函数。维基百科介绍了一个特定的配对函数,即康托配对函数:
备注:三个
As others have made clear, if you plan to implement a pairing function, you may soon find you need arbitrarily large integers (bignums). If you don't want to make a distinction between the pairs (a, b) and (b, a), then sort a and b before applying the pairing function. Actually I lied. You are looking for a bijective ZxZ -> N mapping. Cantor's function only works on non-negative numbers. This is not a problem however, because it's easy to define a bijection f : Z -> N, like so: f(n) = n * 2 if n >= 0 f(n) = -n * 2 - 1 if n < 0
看看这个:http://en.wikipedia.org/wiki/Pigeonhole_principle。如果A, B, C是同一类型,就不能做。如果A和B是16位整数,而C是32位整数,那么您可以简单地使用移位。
哈希算法的本质是它们不能为每个不同的输入提供唯一的哈希。
如果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强制转换是不必要的;重要的是它一开始是无符号空头B。左边的|是无符号的意味着它也将转换为无符号的。
你可以将它用于有符号类型,至少是getA和getB,你可以从combine返回有符号int,但是输入需要0 -extend,所以在C中你需要它们在扩大之前是无符号的short。比如((unsigned)(unsigned空头)A << 16) | (unsigned空头)B
你可能想要使用uint16_t和uint32_t,来定义类型宽度,以匹配你正在使用的移位计数。
这可能吗? 两个整数的组合。它们都有- 2147,483,648到2147,483,647的范围,但你只会看到正数。 2147483647^2 = 4,61169e +18种组合。 因为每个组合都必须是唯一的,并且结果是一个整数,所以您需要某种神奇的整数来包含这个数量的数字。
还是我的逻辑有问题?
我们可以在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)
你可以通过除法和对结果取余来得到每个数字。