algorithm - 从一对 32 位整数到单个 64 位整数是否有一个简单的函数来保持旋转顺序？

Question

这是在将整数坐标点按顺时针顺序排序的上下文中出现的问题，但这个问题与如何进行排序无关。

这个问题是关于二维向量具有自然循环排序的观察结果。具有通常溢出行为的无符号整数（或使用二进制补码的有符号整数）也具有自然循环排序。你能轻松地从第一个排序映射到第二个排序吗？

因此，确切的问题是是否存在从二进制补码有符号 32 位整数对到无符号（或二进制补码有符号）64 位整数的映射，使得任何按顺时针顺序排列的向量列表映射到整数是否按递减（模溢出）顺序？

人们可能会询问的一些技术案例：

• 是的，彼此相乘的向量应该映射到同一事物
• 不，我不在乎哪个向量（如果有）映射到 0
• 不，对映向量的图像不必相差 2^63（尽管这是一个不错的选择）

显而易见的答案是，由于只有大约 0.6*2^64 个不同的坡度，答案是肯定的，这样的地图存在，但我正在寻找一个易于计算的地图。我知道“容易”是主观的，但我真的在寻找合理有效且实施起来并不可怕的东西。因此，特别是，不要计算射线和正 x 轴之间的每个晶格点（除非您知道一种聪明的方法来做到这一点，而无需枚举它们）。

需要注意的重要一点是，它可以通过映射到 6 个5位整数来完成。只需将向量投影到它碰到由x,y=+/-2^62包围的框的位置，然后向负无穷大舍入。您需要 63 位来表示该整数，并且需要另外两个位来编码您击中框的哪一侧。实现需要一点小心，以确保您不会溢出，但只有一个分支和两个划分，否则非常便宜。如果您投影到 2^61，则它不起作用，因为您没有足够的分辨率来分离一些斜率。

此外，在你建议“只使用 atan2”之前，计算atan2(1073741821,2147483643)和atan2(1073741820,2147483641)

编辑：扩展“atan2”评论：

给定两个互质且小于 2^31 的值 x_1 和 x_2（我在示例中使用了 2^31-5 和 2^31-7），我们可以使用扩展欧几里得算法来找到 y_1 和 y_2，使得 y_1 /x_1-y_2/x_2 = 1/(x_1*x_2) ~= 2^-62。由于 arctan 的导数以 1 为界，因此 atan2 的输出在这些值上的差异不会比这更大。因此，有很多向量对不能被 atan2 区分为 vanilla IEEE 754 doubles。

如果您有 80 位扩展寄存器，并且您确定可以在整个计算过程中保留这些寄存器中的驻留（并且不会被上下文切换或只是简单地用完扩展寄存器），那么您很好。但是，我真的不喜欢我的代码的正确性依赖于驻留在扩展寄存器中。

标签： algorithmmath

Answer 1