想象两个正整数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”
这种组合操作也应该是确定的(总是用相同的输入产生相同的结果),并且应该总是在整数的正侧或负侧产生一个整数。
当前回答
假设你有一个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
其他回答
给定正整数A和B,设D = A的位数,E= B的位数 结果可以是D, 0, E, 0, a和B的串联。
示例:A = 300, B = 12。D = 3, E=2 result = 302030012。 这利用了一个事实,即唯一以0开头的数字是0,
优点:易于编码,易于解码,人类可读,有效数字可以先比较,潜在的比较无需计算,简单的错误检查。
缺点:结果的大小是个问题。不过没关系,我们为什么要在电脑里存储无界整数呢。
下面是基于@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
你正在寻找一个双射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位整数,那么您可以简单地使用移位。
哈希算法的本质是它们不能为每个不同的输入提供唯一的哈希。
尽管Stephan202的答案是唯一真正通用的答案,但对于有限范围内的整数,您可以做得更好。例如,如果你的范围是0..1万,那么你可以这样做:
#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更通用的方法效率稍高。它的解码也简单得多;对于初学者来说,不需要平方根:)