以唯一和確定的方式將兩個整數映射為一個假設兩個正整數A和B，我想把這兩個正整數組合成一個整數C。不可能有其他的整數D和E組合到C，所以把它們和加法運算符結合起來就不起作用了。例如：30+10=40=40+0=39+1也不起作用?！?1”+“2”=312=“3”+“12”這種組合操作也應該是確定性的(總是用相同的輸入產生相同的結果)。和應該總是在整數的正反兩面產生一個整數。
3 回答
元芳怎么了
TA貢獻1798條經驗 獲得超7個贊
2NN160 to 2^16 -12^16 * (2^16 -1)2^16 * (2^16 -1)2^32 - 2^1632
Cantor配對函數:
(a + b) * (a + b + 1) / 2 + a; where a, b >= 0
兩個最大的16位整數(65535，65535)的映射將是8589803520，正如您所看到的，這不能適合32位。
a >= b ? a * a + a + b : a + b * b; where a, b >= 0
現在(65535，65535)的映射將是4294967295，正如您所看到的，這是一個32位(0到2^32-1)整數。這就是這個解決方案理想的地方，它只是利用了空間中的每一個點，所以沒有什么能獲得更高的空間效率。
signed 16-(2^15) to 2^15 -1ab0 to 2^15 - 1.
Cantor配對函數:
兩個最大16位有符號整數(32767，32767)的映射將是2147418112，這只是缺少有符號32位整數的最大值。
(32767，32767)=>1073741823，小得多。
Cantor配對函數:
A = a >= 0 ? 2 * a : -2 * a - 1; B = b >= 0 ? 2 * b : -2 * b - 1; (A + B) * (A + B + 1) / 2 + A;
(-32768，-32768)=>8589803520，即64。16位輸入的64位輸出可能是不可原諒的！
Szudzik函數:
A = a >= 0 ? 2 * a : -2 * a - 1; B = b >= 0 ? 2 * b : -2 * b - 1; A >= B ? A * A + A + B : A + B * B;
(-32768，-32768)=>4294967295，對于無符號范圍是32位，對于有符號范圍是64位，但是更好。
A = a >= 0 ? 2 * a : -2 * a - 1; B = b >= 0 ? 2 * b : -2 * b - 1; C = (A >= B ? A * A + A + B : A + B * B) / 2; a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1; (-32768, 32767) => -2147483648 (32767, -32768) => -2147450880 (0, 0) => 0 (32767, 32767) => 2147418112 (-32768, -32768) => 2147483647
2-1.
1632
public static long PerfectlyHashThem(int a, int b)
{
var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}
public static int PerfectlyHashThem(short a, short b)
{
var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}2N4N22N).
慕少森
TA貢獻2019條經驗 獲得超9個贊
int combine(short A, short B)
{
return A<<16 | B;
}
short getA(int C)
{
return C>>16;
}
short getB(int C)
{
return C & 0xFFFF;
}添加回答
舉報
0/150
提交
取消