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

Question

我正在寻找一种快速计算3D Morton数的方法.这个网站有一个基于幻数的技巧,可以用于2D Morton数字,但是如何将它扩展到3D似乎并不明显.

所以基本上我有3个10位数字,我想用最少的操作交错成一个30位数.

Answer 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;

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

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

该技术的工作方式如下.x = ...上面的每一行"将"比特组"分成两半",使得在其间整数的比特之间有足够的空间.例如,如果我们考虑三个4位整数,我们将一个位1234分成000012000034,其中零保留给其他整数.在下一步中,我们以相同的方式分割12和34以获得001002003004.即使10位不能在两组中进行良好的重复划分,您可以将其视为16位,最后丢失最高位.

从第一行可以看出,实际上只需要x它所拥有的每个输入整数x & 0x03000000 == 0.

Answer 2

这是我的python脚本解决方案:

我从他的评论中得到了暗示:Fabian"ryg"Giesen
阅读下面的长评!我们需要跟踪哪些位需要走多远!
然后在每一步中我们选择这些位并移动它们并应用位掩码(请参阅注释最后一行)来掩盖它们!

Bit Distances: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
Bit Distances (binary): ['0', '10', '100', '110', '1000', '1010', '1100', '1110', '10000', '10010']
Shifting bits by 1   for bits idx: []
Shifting bits by 2   for bits idx: [1, 3, 5, 7, 9]
Shifting bits by 4   for bits idx: [2, 3, 6, 7]
Shifting bits by 8   for bits idx: [4, 5, 6, 7]
Shifting bits by 16  for bits idx: [8, 9]
BitPositions: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Shifted bef.:   0000 0000 0000 0000 0000 0011 0000 0000 hex: 0x300
Shifted:        0000 0011 0000 0000 0000 0000 0000 0000 hex: 0x3000000
NonShifted:     0000 0000 0000 0000 0000 0000 1111 1111 hex: 0xff
Bitmask is now: 0000 0011 0000 0000 0000 0000 1111 1111 hex: 0x30000ff

Shifted bef.:   0000 0000 0000 0000 0000 0000 1111 0000 hex: 0xf0
Shifted:        0000 0000 0000 0000 1111 0000 0000 0000 hex: 0xf000
NonShifted:     0000 0011 0000 0000 0000 0000 0000 1111 hex: 0x300000f
Bitmask is now: 0000 0011 0000 0000 1111 0000 0000 1111 hex: 0x300f00f

Shifted bef.:   0000 0000 0000 0000 1100 0000 0000 1100 hex: 0xc00c
Shifted:        0000 0000 0000 1100 0000 0000 1100 0000 hex: 0xc00c0
NonShifted:     0000 0011 0000 0000 0011 0000 0000 0011 hex: 0x3003003
Bitmask is now: 0000 0011 0000 1100 0011 0000 1100 0011 hex: 0x30c30c3

Shifted bef.:   0000 0010 0000 1000 0010 0000 1000 0010 hex: 0x2082082
Shifted:        0000 1000 0010 0000 1000 0010 0000 1000 hex: 0x8208208
NonShifted:     0000 0001 0000 0100 0001 0000 0100 0001 hex: 0x1041041
Bitmask is now: 0000 1001 0010 0100 1001 0010 0100 1001 hex: 0x9249249

x &= 0x3ff
x = (x | x << 16) & 0x30000ff   <<< THIS IS THE MASK for shifting 16 (for bit 8 and 9)
x = (x | x << 8) & 0x300f00f
x = (x | x << 4) & 0x30c30c3
x = (x | x << 2) & 0x9249249

因此,对于10位数和2个交错位(对于32位),您需要执行以下操作!:

x &= 0x3ff
x = (x | x << 16) & 0x30000ff   #<<< THIS IS THE MASK for shifting 16 (for bit 8 and 9)
x = (x | x << 8) & 0x300f00f
x = (x | x << 4) & 0x30c30c3
x = (x | x << 2) & 0x9249249

对于21位数和2个交错位(64位),您需要执行以下操作!:

x &= 0x1fffff
x = (x | x << 32) & 0x1f00000000ffff
x = (x | x << 16) & 0x1f0000ff0000ff
x = (x | x << 8) & 0x100f00f00f00f00f
x = (x | x << 4) & 0x10c30c30c30c30c3
x = (x | x << 2) & 0x1249249249249249

对于42位数和2个交错位(128位),您需要执行以下操作(如果您需要它;-)):

x &= 0x3ffffffffff
x = (x | x << 64) & 0x3ff0000000000000000ffffffffL
x = (x | x << 32) & 0x3ff00000000ffff00000000ffffL
x = (x | x << 16) & 0x30000ff0000ff0000ff0000ff0000ffL
x = (x | x << 8) & 0x300f00f00f00f00f00f00f00f00f00fL
x = (x | x << 4) & 0x30c30c30c30c30c30c30c30c30c30c3L
x = (x | x << 2) & 0x9249249249249249249249249249249L

用于生成和检查交错模式的Python脚本!

def prettyBinString(x,d=32,steps=4,sep=".",emptyChar="0"):
    b = bin(x)[2:]
    zeros = d - len(b)


    if zeros <= 0: 
        zeros = 0
        k = steps - (len(b) % steps)
    else:
        k = steps - (d % steps)

    s = ""
    #print("zeros" , zeros)
    #print("k" , k)
    for i in range(zeros): 
        #print("k:",k)
        if(k%steps==0 and i!= 0):
            s+=sep
        s += emptyChar
        k+=1

    for i in range(len(b)):
        if( (k%steps==0 and i!=0 and zeros == 0) or  (k%steps==0 and zeros != 0) ):
            s+=sep
        s += b[i]
        k+=1
    return s    

def binStr(x): return prettyBinString(x,32,4," ","0")


def computeBitMaskPatternAndCode(numberOfBits, numberOfEmptyBits):
    bitDistances=[ i*numberOfEmptyBits for i in range(numberOfBits) ]
    print("Bit Distances: " + str(bitDistances))
    bitDistancesB = [bin(dist)[2:] for dist in  bitDistances]
    print("Bit Distances (binary): " + str(bitDistancesB))
    moveBits=[] #Liste mit allen Bits welche aufsteigend um 2, 4,8,16,32,64,128 stellen geschoben werden müssen

    maxLength = len(max(bitDistancesB, key=len))
    abort = False
    for i in range(maxLength):
        moveBits.append([])
        for idx,bits in enumerate(bitDistancesB):
            if not len(bits) - 1 < i:
                if(bits[len(bits)-i-1] == "1"):
                    moveBits[i].append(idx)

    for i in range(len(moveBits)):
        print("Shifting bits by " + str(2**i) + "\t for bits idx: " + str(moveBits[i]))

    bitPositions = range(numberOfBits);
    print("BitPositions: " + str(bitPositions))
    maskOld = (1 << numberOfBits) -1

    codeString = "x &= " + hex(maskOld) + "\n"
    for idx in xrange(len(moveBits)-1, -1, -1):
        if len(moveBits[idx]):


           shifted = 0
           for bitIdxToMove in moveBits[idx]:
                shifted |= 1<<bitPositions[bitIdxToMove];
                bitPositions[bitIdxToMove] += 2**idx; # keep track where the actual bit stands! might get moved several times

           # Get the non shifted part!     
           nonshifted = ~shifted & maskOld

           print("Shifted bef.:\t" + binStr(shifted) + " hex: " + hex(shifted))
           shifted = shifted << 2**idx
           print("Shifted:\t" + binStr(shifted)+ " hex: " + hex(shifted))

           print("NonShifted:\t" + binStr(nonshifted) + " hex: " + hex(nonshifted))
           maskNew =  shifted | nonshifted
           print("Bitmask is now:\t" + binStr(maskNew) + " hex: " + hex(maskNew) +"\n")
           #print("Code: " + "x = x | x << " +str(2**idx)+ " & " +hex(maskNew))

           codeString += "x = (x | x << " +str(2**idx)+ ") & " +hex(maskNew) + "\n"
           maskOld = maskNew
    return codeString


numberOfBits = 10;
numberOfEmptyBits = 2;
codeString = computeBitMaskPatternAndCode(numberOfBits,numberOfEmptyBits);
print(codeString)

def partitionBy2(x):
    exec(codeString)
    return x

def checkPartition(x):
    print("Check partition for: \t" + binStr(x))
    part = partitionBy2(x);
    print("Partition is : \t\t" + binStr(part))
    #make the pattern manualy
    partC = long(0);
    for bitIdx in range(numberOfBits):
        partC  = partC | (x & (1<<bitIdx)) << numberOfEmptyBits*bitIdx
    print("Partition check is :\t" + binStr(partC))
    if(partC == part):
        return True
    else:
        return False

checkError = False        
for i in range(20):
    x = random.getrandbits(numberOfBits);
    if(checkPartition(x) == False):
        checkError = True
        break
if not checkError:
    print("CHECK PARTITION SUCCESSFUL!!!!!!!!!!!!!!!!...")
else:
    print("checkPartition has ERROR!!!!")

我会在一段时间内添加解码代码!

Answer 3

最简单的可能是查找表,如果你有4K可用空间:

static uint32_t t [ 1024 ] = { 0, 0x1, 0x8, ... };

uint32_t m ( int a, int b, int c )
{
    return t[a] | ( t[b] << 1 ) | ( t[c] << 2 );
}

比特黑客使用移位和掩码来扩展比特,因此每次它移动值并将其移位,将一些比特复制到空白区域,然后屏蔽掉组合,这样只保留原始比特.

例如:

x = 0xabcd;
  = 0000_0000_0000_0000_1010_1011_1100_1101    

x = (x | (x << S[3])) & B[3]; 

  = ( 0x00abcd00 | 0x0000abcd ) & 0xff00ff 
  = 0x00ab__cd & 0xff00ff 
  = 0x00ab00cd
  = 0000_0000_1010_1011_0000_0000_1100_1101
x = (x | (x << S[2])) & B[2]; 
  = ( 0x0ab00cd0 | 0x00ab00cd) & 0x0f0f0f0f 
  =   0x0a_b_c_d & 0x0f0f0f0f 
  = 0x0a0b0c0d 
  = 0000_1010_0000_1011_0000_1100_0000_1101
x = (x | (x << S[1])) & B[1]; 
  = ( 0000_1010_0000_1011_0000_1100_0000_1101 | 
      0010_1000_0010_1100_0011_0000_0011_0100 ) &
      0011_0011_0011_0011_0011_0011_0011_0011
  =   0010_0010_0010_0011_0011_0000_0011_0001
x = (x | (x << S[0])) & B[0]; 
  = ( 0010_0010_0010_0011_0011_0000_0011_0001 | 
      0100_0100_0100_0110_0110_0000_0110_0010 ) &
      0101_0101_0101_0101_0101_0101_0101_0101
  =   0100_0010_0100_0101_0101_0000_0101_0001

在每次迭代中,每个块被分成两部分,块的最左半部分的最右边的位移动到其最终位置,并且应用掩模,因此仅保留所需的位.

一旦你将输入间隔开,移动它们使得一个值落入另一个的零值很容易.

要在最终结果中的值之间扩展该技术超过两位,您必须增加位最终之间的位移.它有点棘手,因为起始块大小不是2的幂,所以你可以将它分成中间,或者2的边界.

所以这样的演变可能有效:

0000_0000_0000_0000_0000_0011_1111_1111    
0000_0011_0000_0000_0000_0000_1111_1111    
0000_0011_0000_0000_1111_0000_0000_1111    
0000_0011_0000_1100_0011_0000_1100_0011    
0000_1001_0010_0100_1001_0010_0100_1001    

// 0000_0000_0000_0000_0000_0011_1111_1111    
x = ( x | ( x << 16 ) ) & 0x030000ff;
// 0000_0011_0000_0000_0000_0000_1111_1111    
x = ( x | ( x << 8 ) ) & 0x0300f00f;
// 0000_0011_0000_0000_1111_0000_0000_1111    
x = ( x | ( x << 4 ) ) & 0x030c30c3;
// 0000_0011_0000_1100_0011_0000_1100_0011    
x = ( x | ( x << 2 ) ) & 0x09249249;
// 0000_1001_0010_0100_1001_0010_0100_1001    

对输入执行相同的转换,逐个移动,另一个移动,或者它们一起移动,你就完成了.

Answer 4

我对上面的内容进行了修改，将 3 个 16 位数字组合成一个 48 位（实际上是 64 位）数字。也许它会节省一些人到达那里的思考。

#include <inttypes.h>
#include <assert.h>
uint64_t zorder3d(uint64_t x, uint64_t y, uint64_t z){
     static const uint64_t B[] = {0x00000000FF0000FF, 0x000000F00F00F00F,
                                    0x00000C30C30C30C3, 0X0000249249249249};           
     static const int S[] =  {16, 8, 4, 2}; 
     static const uint64_t MAXINPUT = 65536;

     assert( ( (x < MAXINPUT) ) && 
      ( (y < MAXINPUT) ) && 
      ( (z < MAXINPUT) )
     );

     x = (x | (x << S[0])) & B[0];
     x = (x | (x << S[1])) & B[1];
     x = (x | (x << S[2])) & B[2];
     x = (x | (x << S[3])) & B[3];

     y = (y | (y << S[0])) & B[0];
     y = (y | (y << S[1])) & B[1];
     y = (y | (y << S[2])) & B[2];
     y = (y | (y << S[3])) & B[3];

     z = (z | (z <<  S[0])) & B[0];
     z = (z | (z <<  S[1])) & B[1];
     z = (z | (z <<  S[2])) & B[2];
     z = (z | (z <<  S[3])) & B[3];

     return ( x | (y << 1) | (z << 2) );
    }

Answer 5

好时机,我上个月就这么做了!

关键是要做两个功能.一个扩展到每三位一位.然后我们可以将它们中的三个组合在一起(最后两个移位)以获得最终的Morton交错值.

此代码从HIGH位开始交错(对于固定点值更为合理.)如果您的应用程序每个组件只有10位,只需将每个值左移22,以使其从高位开始.

/* Takes a value and "spreads" the HIGH bits to lower slots to seperate them.
   ie, bit 31 stays at bit 31, bit 30 goes to bit 28, bit 29 goes to bit 25, etc.
   Anything below bit 21 just disappears. Useful for interleaving values
   for Morton codes. */
inline unsigned long spread3(unsigned long x)
{
  x=(0xF0000000&x) | ((0x0F000000&x)>>8) | (x>>16); // spread top 3 nibbles
  x=(0xC00C00C0&x) | ((0x30030030&x)>>4);
  x=(0x82082082&x) | ((0x41041041&x)>>2);
  return x;
}

inline unsigned long morton(unsigned long x, unsigned long y, unsigned long z)
{
  return spread3(x) | (spread3(y)>>1) | (spread3(z)>>2);
}