如何計算三維莫頓數（交織3位整數）

Question

我正在尋找計算3D莫頓數的快速方法。這個網站有一個基於魔術數字的二維莫頓數字，但它似乎並不明顯如何將其擴展到3D：http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

所以基本上我有3個10位數字，我想交織以最少的操作數量轉換爲單個30位數字。

Answer 1

您可以使用相同的技術。我假設變量包含32位整數，其中最高的22位設置爲0（這比限制性更強）。對於包含三個10位整數的一個每個變量x我們執行下列操作：

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

最簡單的可能是一個查找表，如果你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); 
} 

位黑客利用的變化和口罩傳播位了，所以每次它改變的價值和它ORS ，將一些比特複製到空白空間中，然後掩蓋組合，只保留原始比特。

例如：

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 3

下面的代碼找到三個10位輸入數字的莫頓數。它使用鏈接中的idee並在步驟5-5,3-2-3-2,2-1-1-1-2-1-1-1和1-1-1- 1-1-1-1-1-1-1因爲10不是二的冪。

......................
............98765..........
........987....56......432....10 
......98..7..5..6....43..2..1..0 
....9..8..7..5..6..4..3..2..1..0 

上面你可以看到每個位在第一個和第四個步驟之後的位置。

public static Int32 GetMortonNumber(Int32 x, Int32 y, Int32 z) 
{ 
    return SpreadBits(x, 0) | SpreadBits(y, 1) | SpreadBits(z, 2); 
} 

public static Int32 SpreadBits(Int32 x, Int32 offset) 
{ 
    if ((x < 0) || (x > 1023)) 
    { 
     throw new ArgumentOutOfRangeException(); 
    } 

    if ((offset < 0) || (offset > 2)) 
    { 
     throw new ArgumentOutOfRangeException(); 
    } 

    x = (x | (x << 10)) & 0x000F801F; 
    x = (x | (x << 4)) & 0x00E181C3; 
    x = (x | (x << 2)) & 0x03248649; 
    x = (x | (x << 2)) & 0x09249249; 

    return x << offset; 
} 

Answer 4

好時機，我剛剛做了這個上個月！

關鍵是做出兩個功能。一位將位分散到每三位。 然後我們可以將它們中的三個結合在一起（最後兩個換檔），以獲得最終的Morton交錯值。

此代碼交替開始於高位（對定點值而言更爲合理）。如果您的應用程序僅爲每個組件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); 
} 

Answer 5

我採取了上述和修改它將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 6

這裏的一個發生器我在紅寶石製成用於製造任意長度的編碼方法：

def morton_code_for(bits) 
    method = '' 

    limit_mask = (1 << (bits * 3)) - 1 
    split = (2 ** ((Math.log(bits)/Math.log(2)).to_i + 1)).to_i 
    level = 1 

    puts "// Coding for 3 #{bits}-bit values" 

    loop do 
    shift = split 
    split /= 2 
    level *= 2 

    mask = ([ '1' * split ] * level).join('0' * split * 2).to_i(2) & limit_mask 

    expression = "v = (v | (v << %2d)) & 0x%016x;" % [ shift, mask ] 

    method << expression 

    puts "%s // 0b%064b" % [ expression, mask ] 

    break if (split <= 1) 
    end 

    puts 
    print "// Test of method results: " 
    v = (1 << bits) - 1 
    puts eval(method).to_s(2) 
end 

morton_code_for(21) 

輸出是適當地通用的，可以根據需要進行調整。示例輸出：

// Coding for 3 21-bit values 
v = (v | (v << 32)) & 0x7fff00000000ffff; // 0b0111111111111111000000000000000000000000000000001111111111111111 
v = (v | (v << 16)) & 0x00ff0000ff0000ff; // 0b0000000011111111000000000000000011111111000000000000000011111111 
v = (v | (v << 8)) & 0x700f00f00f00f00f; // 0b0111000000001111000000001111000000001111000000001111000000001111 
v = (v | (v << 4)) & 0x30c30c30c30c30c3; // 0b0011000011000011000011000011000011000011000011000011000011000011 
v = (v | (v << 2)) & 0x1249249249249249; // 0b0001001001001001001001001001001001001001001001001001001001001001 

// Test of method results: 1001001001001001001001001001001001001001001001001001001001001 

Answer 7

以下是用於爲三維點生成大小爲64位的Morton密鑰的代碼片段。

using namespace std; 

unsigned long long spreadBits(unsigned long long x) 
{ 
    x=(x|(x<<20))&0x000001FFC00003FF; 
    x=(x|(x<<10))&0x0007E007C00F801F; 
    x=(x|(x<<4))&0x00786070C0E181C3; 
    x=(x|(x<<2))&0x0199219243248649; 
    x=(x|(x<<2))&0x0649249249249249; 
    x=(x|(x<<2))&0x1249249249249249; 
    return x; 
} 

int main() 
{ 
    unsigned long long x,y,z,con=1; 
    con=con<<63; 
    printf("%#llx\n",(spreadBits(x)|(spreadBits(y)<<1)|(spreadBits(z)<<2))|con);  
} 

Answer 8

我今天有一個類似的問題，但不是3個數字，我必須合併任意數量的任意位數的數字。我使用了我自己的一種位擴散和屏蔽算法，並將其應用於C＃BigIntegers。這是我寫的代碼。作爲編譯步驟，它可以計算給定維數和位深度的幻數和掩碼。然後，您可以重複使用該對象進行多次轉化。

/// <summary> 
/// Convert an array of integers into a Morton code by interleaving the bits. 
/// Create one Morton object for a given pair of Dimension and BitDepth and reuse if when encoding multiple 
/// Morton numbers. 
/// </summary> 
public class Morton 
{ 
    /// <summary> 
    /// Number of bits to use to represent each number being interleaved. 
    /// </summary> 
    public int BitDepth { get; private set; } 

    /// <summary> 
    /// Count of separate numbers to interleave into a Morton number. 
    /// </summary> 
    public int Dimensions { get; private set; } 

    /// <summary> 
    /// The MagicNumbers spread the bits out to the right position. 
    /// Each must must be applied and masked, because the bits would overlap if we only used one magic number. 
    /// </summary> 
    public BigInteger LargeMagicNumber { get; private set; } 
    public BigInteger SmallMagicNumber { get; private set; } 

    /// <summary> 
    /// The mask removes extraneous bits that were spread into positions needed by the other dimensions. 
    /// </summary> 
    public BigInteger Mask { get; private set; } 

    public Morton(int dimensions, int bitDepth) 
    { 
     BitDepth = bitDepth; 
     Dimensions = dimensions; 
     BigInteger magicNumberUnit = new BigInteger(1UL << (int)(Dimensions - 1)); 
     LargeMagicNumber = magicNumberUnit; 
     BigInteger maskUnit = new BigInteger(1UL << (int)(Dimensions - 1)); 
     Mask = maskUnit; 
     for (var i = 0; i < bitDepth - 1; i++) 
     { 
      LargeMagicNumber = (LargeMagicNumber << (Dimensions - 1)) | (i % 2 == 1 ? magicNumberUnit : BigInteger.Zero); 
      Mask = (Mask << Dimensions) | maskUnit;  
     } 
     SmallMagicNumber = (LargeMagicNumber >> BitDepth) << 1; // Need to trim off pesky ones place bit. 
    } 

    /// <summary> 
    /// Interleave the bits from several integers into a single BigInteger. 
    /// The high-order bit from the first number becomes the high-order bit of the Morton number. 
    /// The high-order bit of the second number becomes the second highest-ordered bit in the Morton number. 
    /// 
    /// How it works. 
    /// 
    /// When you multupliy by the magic numbers you make multiple copies of the the number they are multplying, 
    /// each shifted by a different amount. 
    /// As it turns out, the high order bit of the highest order copy of a number is N bits to the left of the 
    /// second bit of the second copy, and so forth. 
    /// This is because each copy is shifted one bit less than N times the copy number. 
    /// After that, you apply the AND-mask to unset all bits that are not in position. 
    /// 
    /// Two magic numbers are needed because since each copy is shifted one less than the bitDepth, consecutive 
    /// copies would overlap and ruin the algorithm. Thus one magic number (LargeMagicNumber) handles copies 1, 3, 5, etc, while the 
    /// second (SmallMagicNumber) handles copies 2, 4, 6, etc. 
    /// </summary> 
    /// <param name="vector">Integers to combine.</param> 
    /// <returns>A Morton number composed of Dimensions * BitDepth bits.</returns> 
    public BigInteger Interleave(int[] vector) 
    { 
     if (vector == null || vector.Length != Dimensions) 
      throw new ArgumentException("Interleave expects an array of length " + Dimensions, "vector"); 
     var morton = BigInteger.Zero; 
     for (var i = 0; i < Dimensions; i++) 
     { 
      morton |= (((LargeMagicNumber * vector[i]) & Mask) | ((SmallMagicNumber * vector[i]) & Mask)) >> i; 
     } 
     return morton; 
    } 


    public override string ToString() 
    { 
     return "Morton(Dimension: " + Dimensions + ", BitDepth: " + BitDepth 
      + ", MagicNumbers: " + Convert.ToString((long)LargeMagicNumber, 2) + ", " + Convert.ToString((long)SmallMagicNumber, 2) 
      + ", Mask: " + Convert.ToString((long)Mask, 2) + ")"; 
    } 
} 

Answer 9

這裏是我的解決方案與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 

而對於一個42bit號和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!!!!") 

我會在一段時間內添加解碼代碼！