如何计算一个三维莫顿数（交织的3个整数的比特） [英] How to compute a 3D Morton number (interleave the bits of 3 ints)

问题描述

我正在寻找一个快速的方法来计算一个3D莫顿数。这个网站有一个基础的魔法数字把戏做它的2D莫顿的数字，但它似乎并不明显如何将其扩展到3D：<一href="http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN">http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

I'm looking for a fast way to compute a 3D Morton number. This site has a magic-number based trick for doing it for 2D Morton numbers, but it doesn't seem obvious how to extend it to 3D: http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

所以基本上我有我想要交错与操作最​​少数量的一个30位的数字3的​​10位数字。

So basically I have 3 10-bit numbers that I want to interleave into a single 30 bit number with a minimal number of operations.

推荐答案

您可以使用同样的技术。我假设变量包含32位整数，最高的22位设置为 0 （这是更严格的比需要一点）。对于每个变量 X 包含3个10位整数，我们执行下列操作之一：

You can use the same technique. I'm assuming that variables contain 32-bit integers with the highest 22 bits set to 0 (which is a bit more restrictive than necessary). For each variable x containing one of the three 10-bit integers we do the following:

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

然后，用 X ，是和以Z 三操纵10位整数，我们采取得到的结果：

Then, with x,y and z the three manipulated 10-bit integers we get the result by taking:

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

这种技术的工作方式如下。每个上述X = ... 线分割比特组中的一半，使得有足够的空间在之间的其它整数的比特。举例来说，如果我们考虑三个4位整数，我们分手之一，位1234到000012000034，其中零被保留用于其它整数。在接下来的步骤中，我们分成12和34用同样的方法来获得001002003004.尽管10位不会使一个不错的重复部一分为二组，你可以认为这是16位的，你失去了最高的人到底

The way this technique works is as follows. Each of the x = ... lines above "splits" groups of bits in half such that there is enough space in between for the bits of the other integers. For example, if we consider three 4-bit integers, we split one with bits 1234 into 000012000034 where the zeros are reserved for the other integers. In the next step we split 12 and 34 in the same way to get 001002003004. Even though 10 bits doesn't make for a nice repeated division in two groups, you can just consider it 16 bits where you lose the highest ones in the end.

正如你可以从第一行看，你实际上只需要一个为每个输入整数 X 它认为 X'放大器; 0x03000000 == 0 。

As you can see from the first line, you actually only need that for each input integer x it holds that x & 0x03000000 == 0.

这篇关于如何计算一个三维莫顿数（交织的3个整数的比特）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！