由两个整数生成一个独特的整数

[wdc63]

我有两个整数 a 、b 。我想得到一个独特的整数 c ，让 a 、b 任何一个发生变化时，c 的值都是独特唯一的，且不需要反运算，即无需通过 c 得到 a 、b 。 我想到的方法是 a*(b 的位数+1) + b ，例如 123,234=123*1000+234=123234 。 由于我的程序中有大量的这种运算，请问各位大佬对此有没有经验，提供一个开销最小最小最小的算法。

[learningman]

你想的这个，(123,234)和(12.3234)得到的结果是一样的
推荐随便找个 StringHash 算法

[wdc63]

@learningman 只可能是整数，但是我发现有负数存在也会出现错误。另外在网上找到了这是个数学问题，配对函数，其中最出名的康拓尔配对函数：Pi(x,y)=(x+y)(x+y+1)/2+y ，但是也只支持自然数。

[lsylsy2]

让 a 、b 任何一个发生变化时，c 的值都是独特唯一的，且不需要反运算，即无需通过 c 得到 a 、b 。

你这其实是很经典的数字签名的场景，不过有一个问题：“独特唯一”其实是没有必要的，哪怕是网银的金融级别，也只是“重复的概率小到忽略不计”而已。

你的“运算量”和“对独特唯一的要求”具体是多少？根据这两个要求挑选一个合适的签名算法或者哈希算法就行

[copper20]

假设你的 a b c 都是 int64 ，那么这个需求是不可能实现的。这个函数

f: int64 x int64 -> int64

定义域的基数远大于陪域的基数，就不可能是一个单射，是必然会发生碰撞的

如果 a b c 都来自全体自然数集，那按康托尔的那个配对函数来就行了

[wdc63]

@copper20 有负数，康托尔算法不支持。另外 a 、b 都在 10W 以下，合理的算法 c 值应该不会超出 int32 的范围吧。

[copper20]

@copper20 如果 a b c 都来自全体整数的话就可以先把整数集映射一一映射到自然数集然后再套康托尔那个函数

if z >= 0, f(z) = 2 * z
if z < 0, f(z) = 2 * -z - 1

[wdc63]

@lsylsy2 需要大概单线程 1 毫秒 10 万级别

[wdc63]

@copper20 谢谢，我按这个试试效率以及会不会溢出。

[wxf666]

@wdc63 a, b 都在 10W 以下，那么共有 10W ^ 2 = 100 亿 种可能 > uint32 ≈ 42 亿，不可能不超出 int32 范围？

[zk8802]

单线程每秒生成 10 ^ 8 个数，不考虑程序中具体实现和调用的开销的话（例如 CPython 就别想了），一般的快速哈希算法应该都可以满足楼主的要求。

随便举一个例子： https://github.com/Cyan4973/xxHash

[Jooooooooo]

不要自己发明这种算法.

[LaTero]

想要结果唯一，那结果一定是输入的位数的两倍以上。最直觉的方法，假设 a 和 b 32 位，结果 64 位
((int64)a << 32)+(int64)b
速度非常快，和正负数或者补码 /反码无关

[wdc63]

@LaTero 谢谢，你的算法应该不能保证结果是唯一的。

[wdc63]

static int szudzikPair(int x, int y)
{

return (x >= y ? (x * x) + x + y : (y * y) + x);
}

static int szudzikPairSigned(int x, int y)
{

int a = (x >= 0 ? 2 * x : (-2 * x) - 1);
int b = (y >= 0 ? 2 * y : (-2 * y) - 1);
return szudzikPair(a, b) / 2;
}

5800x 单线程 10w 次（ x 、y 均为负数）大概 3ms

[wdc63]

@wdc63 debug 模式

[wxf666]

@wdc63

> @LaTero 的算法应该不能保证结果是唯一的

这不就是你的 a*(b 的位数+1) + b 的二进制版么。。

要不，举个反例？

[wdc63]

@wxf666 是的，那使用 ulong 就行。

[wdc63]

@wxf666 存在负数就会出现碰撞。

[LaTero]

@wdc63 怎么碰撞？这算法这不就是把两个 32 位拼成 64 位？ a 在高 32 位 b 在低位，别说负数，这算法浮点数也能用（可能会有 NaN 等)

[crab]

类似用鼠标消息坐标 高低端存储 xy 坐标