这是一个创建于 800 天前的主题，其中的信息可能已经有所发展或是发生改变。
我有两个整数 a 、b 。我想得到一个独特的整数 c ，让 a 、b 任何一个发生变化时，c 的值都是独特唯一的，且不需要反运算，即无需通过 c 得到 a 、b 。 我想到的方法是 a*(b 的位数+1) + b ，例如 123,234=123*1000+234=123234 。 由于我的程序中有大量的这种运算，请问各位大佬对此有没有经验，提供一个开销最小最小最小的算法。
 |
1
learningman 2022-09-11 15:15:16 +08:00
你想的这个，(123,234)和(12.3234)得到的结果是一样的
推荐随便找个 StringHash 算法 |
 |
2
wdc63 OP @learningman 只可能是整数，但是我发现有负数存在也会出现错误。另外在网上找到了这是个数学问题，配对函数，其中最出名的康拓尔配对函数：Pi(x,y)=(x+y)(x+y+1)/2+y ，但是也只支持自然数。
|
 |
3
lsylsy2 2022-09-11 15:27:19 +08:00
让 a 、b 任何一个发生变化时，c 的值都是独特唯一的，且不需要反运算，即无需通过 c 得到 a 、b 。
你这其实是很经典的数字签名的场景，不过有一个问题：“独特唯一”其实是没有必要的，哪怕是网银的金融级别，也只是“重复的概率小到忽略不计”而已。 你的“运算量”和“对独特唯一的要求”具体是多少？根据这两个要求挑选一个合适的签名算法或者哈希算法就行 |
 |
4
copper20 2022-09-11 15:28:18 +08:00  3
假设你的 a b c 都是 int64 ，那么这个需求是不可能实现的。这个函数
f: int64 x int64 -> int64 定义域的基数远大于陪域的基数，就不可能是一个单射，是必然会发生碰撞的 如果 a b c 都来自全体自然数集，那按康托尔的那个配对函数来就行了 |
|
5
wdc63 OP @copper20 有负数，康托尔算法不支持。另外 a 、b 都在 10W 以下，合理的算法 c 值应该不会超出 int32 的范围吧。
|
|
6
copper20 2022-09-11 15:32:40 +08:00
@copper20 如果 a b c 都来自全体整数的话就可以先把整数集映射一一映射到自然数集然后再套康托尔那个函数
if z >= 0, f(z) = 2 * z if z < 0, f(z) = 2 * -z - 1 |
 |
9
wxf666 2022-09-11 15:47:32 +08:00
@wdc63 a, b 都在 10W 以下，那么共有 10W ^ 2 = 100 亿 种可能 > uint32 ≈ 42 亿，不可能不超出 int32 范围？
|
 |
10
zk8802 2022-09-11 15:51:07 +08:00
单线程每秒生成 10 ^ 8 个数，不考虑程序中具体实现和调用的开销的话（例如 CPython 就别想了），一般的快速哈希算法应该都可以满足楼主的要求。
随便举一个例子： https://github.com/Cyan4973/xxHash |
 |
11
Jooooooooo 2022-09-11 15:53:27 +08:00
不要自己发明这种算法.
|
 |
12
LaTero 2022-09-11 15:54:17 +08:00 via Android
想要结果唯一，那结果一定是输入的位数的两倍以上。最直觉的方法，假设 a 和 b 32 位，结果 64 位
((int64)a << 32)+(int64)b 速度非常快，和正负数或者补码 /反码无关 |
|
14
wdc63 OP 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 |
|
16
wxf666 2022-09-11 16:11:55 +08:00
|
|
19
LaTero 2022-09-11 16:16:47 +08:00 via Android
@wdc63 怎么碰撞？这算法这不就是把两个 32 位拼成 64 位？ a 在高 32 位 b 在低位，别说负数，这算法浮点数也能用（可能会有 NaN 等)
|
 |
20
crab 2022-09-11 16:17:38 +08:00
类似用鼠标消息坐标 高低端存储 xy 坐标
|
|
21
LaTero 2022-09-11 16:22:35 +08:00 via Android
@wdc63 另外数学版本 f(a,b)=a*2^32+b, a,b∈Z∩[-2^31, 2^31-1]也不会碰撞
|
 |
23
xuanbg 2022-09-11 16:34:47 +08:00
不对 A 、B 的性质加以限制的话，无论是加法、乘法还是他们的组合，无论如何组合，都无法保证结果的唯一性。
|
 |
25
chenzhekl 2022-09-11 19:45:08 +08:00
lz 给的算法也不是一个单射，反例：(123, 234) -> (123234), (12, 3234) -> (123234)。 @copper20 提到的 Cantor pairing function 应该是最好的选择了吧，不然就用哈希函数，然后自己处理极小概率的哈希碰撞。
|
|
26
wdc63 OP @chenzhekl 我用的 LaTero 的算法： ((int64)a << 32)+(int64)b ，实测比康托尔配对函数快一倍，而且康托尔配对函数在 int32 范围内最大支持到 25000 左右。
|
 |
27
mlhadoop 2022-09-11 20:55:33 +08:00
+ 运算符 不就好了。？
|
 |
28
mengzhuo 2022-09-11 21:47:45 +08:00
这个简单，wyhash 的原理，设大质数 P1 P2
h1, h2 = (a xor P1) * (b xor P2) hash = h1 * h2 https://github.com/wangyi-fudan/wyhash |
 |
29
lrjia 2022-09-12 00:22:51 +08:00
直接用位运算，可能还会更快一些 ((int64)a << 32) & (int64)b
|
 |
30
mxT52CRuqR6o5 2022-09-12 00:24:06 +08:00 via Android
直接连起来不就好了
|
 |
32
aguesuka 2022-09-13 12:09:48 +08:00
long merge(int a, int b){
int pair[2] = {a, b}; return *((long*) &pair); } 这个方法不用位运算, 也许是最快的. 不过也许您应该考虑使用 struct 或者 union |
Select Language