寻求保留旋转序的32位补码整数对到64位整数的高效映射函数

核心结论 #

题目中提到的正方形边界投影映射方案，是完全符合所有技术约束、计算成本极低的可落地方案，不存在需要枚举格点的额外开销。

方案具体实现逻辑 #

对任意非零32位补码整数向量 (x, y)：

• 取大小为 ±2^62 的正方形作为投影边界，计算缩放系数，将向量按负无穷取整的规则缩放，直到刚好命中正方形的某条边界。
• 用2个二进制位标识向量命中的边界类型（x正边、x负边、y正边、y负边，刚好覆盖4个象限的方向归属），剩余的二进制位存储边界上的取整缩放值，最终拼接为64位整数作为映射结果。
• 在投影边界上按照顺时针方向为所有投影点赋值时，最终得到的映射值序列，天然满足「顺时针排列的向量对应模溢出意义下的降序值」的核心需求。

方案合规性说明 #

• 天然满足成比例向量的映射要求：互成倍数的向量属于同一条射线方向，投影到边界上的取整值完全一致，不需要额外做最大公约数归一化。
• 计算开销可控：整个流程仅包含1次分支判断（确定向量命中的是x轴方向边界还是y轴方向边界）、2次整数除法，没有浮点运算，不需要遍历枚举射线经过的格点。
• 边界尺度选择的必要性：如果把投影边界缩小到 ±2^{61，会因为分辨率不足，无法区分斜率差极小的不同向量，直接导致映射失效，因此必须保持2}62的边界尺度，才能匹配32位输入向量的方向分辨率。

为什么不推荐atan2角度映射方案 #

该方案存在无法规避的精度缺陷，不能作为生产逻辑的依赖：

• 取两个接近2^31的互质x值（例如2^31-5和2^31-7），通过扩展欧几里得算法可以构造出对应的y值，使得两个向量的斜率差仅为1/(x1*x2)≈2^-62，对应的角度差也处于同个量级。
• 标准IEEE 754双精度浮点数仅52位尾数，根本无法区分这个量级的角度差，会把不同斜率的向量映射为完全相同的值。
• 即便是精度更高的80位扩展浮点格式，也无法保证计算全程数据驻留在CPU寄存器中，一旦因为上下文切换、寄存器资源抢占被换出到内存，就会触发精度截断，逻辑正确性没有可靠保障。

加分特性参考：如果调整边界上排序的偏移量，很容易实现对跖向量映射值严格相差2^63的效果，不需要额外增加计算成本。

内容的提问来源于stack exchange，提问作者Aubrey da Cunha