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

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

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


当前回答

你的建议是不可能的。总会有碰撞。

为了将两个对象映射到另一个单独的集合,映射的集合必须具有预期组合数量的最小大小:

假设有一个32位整数,则有2147483647个正整数。选择其中两个顺序无关紧要且具有重复的组合,将得到2305843008139952128个组合。这并不适合32位整数的集合。

不过,你可以把这个映射压缩成61位。使用64位整数可能是最简单的。将高的字设置为较小的整数,低的字设置为较大的整数。

其他回答

如果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,来定义类型宽度,以匹配你正在使用的移位计数。

假设a是第一个,b是第二个。设p是a+1个质数,q是b+1个质数

然后,如果a<b,结果是pq,如果a>b,结果是2pq。如果a=b,让它是p^2。

看看这个:http://en.wikipedia.org/wiki/Pigeonhole_principle。如果A, B, C是同一类型,就不能做。如果A和B是16位整数,而C是32位整数,那么您可以简单地使用移位。

哈希算法的本质是它们不能为每个不同的输入提供唯一的哈希。

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

正整数的标准数学方法是利用质因数分解的唯一性。

f( x, y ) -> 2^x * 3^y

缺点是,图像往往跨越相当大的整数范围,因此当涉及到在计算机算法中表示映射时,您可能会在为结果选择适当的类型时遇到问题。

你可以修改它来处理负x和负y,通过编码一个5和7次幂项的标志。

e.g.

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)