一尘不染

如何计算3D莫顿数(交错3个整数的位)

algorithm

我正在寻找一种计算3D莫顿数的快速方法。这个站点有一个基于魔术数的技巧来为2D莫顿数做,但是如何将其扩展到3D似乎并不明显。

因此,基本上我有3个10位数字,我希望通过最少的操作将它们交织成一个30位数字。


阅读 257

收藏
2020-07-28

共1个答案

一尘不染

您可以使用相同的技术。我假设变量包含32位整数,并将最高22位设置为0(这比必要性要严格一些)。对于x包含三个10位整数之一的每个变量,我们执行以下操作:

x = (x | (x << 16)) & 0x030000FF;
x = (x | (x <<  8)) & 0x0300F00F;
x = (x | (x <<  4)) & 0x030C30C3;
x = (x | (x <<  2)) & 0x09249249;

然后,用xyz三个操纵10位整数,我们通过采取得到的结果:

x | (y << 1) | (z << 2)

该技术的工作方式如下。x = ...上方的每一行将位组“拆分”成两半,以使它们之间有足够的空间容纳其他整数的位。例如,如果我们考虑三个4位整数,则将一个带有1234位的整数拆分为000012000034,其中零保留给其他整数。在下一步中,我们以相同的方式将12和34拆分为001002003004。即使10位并不能很好地将两组重复划分,您也可以将其视为16位,最后丢失最高位。

从第一行可以看到,对于每个输入整数,实际上只需要x它即可x & 0x03000000 == 0

2020-07-28