如何计算3D莫顿数（交织的3个整数的比特）如何计算3D莫顿数（交织的3个整数的比特）(How to

2019-05-13 14:24发布

站内文章 / 前端开发

51 0

女痞

女 | 书童

私信

我正在寻找一个快速的方法来计算3D莫顿数。这个网站有这样做的2D莫顿数字的魔术数字基于伎俩，但它似乎并不明显如何将其扩展到三维。

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

Answer 1:

您可以使用相同的技术。我假设变量包含与设置为最高22位的32位整数0 （这是一个比较限制性比必要）。对于每个变量x含有我们做以下的3个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脚本的解决方案：

我心领神会从他的评论：法比安“RYG”吉森
阅读下面的长注释！我们需要跟踪哪个位需要走多远！
然后在每个步骤中，我们选择这些位并将其移动和应用位掩码（见注释最后一行），以掩盖他们！

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!!!!")

我将添加解码程序代码，以及在一段时间！

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 );
}

该位黑客利用的变化和口罩传播位了，所以每次它改变的价值和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 4:

好时机，我只是做了这最后一个月！

关键是让两种功能。一个扩展位出每一个三分位。然后，我们可以（与最后两个转变）相结合他们三人得到最终莫顿交错值。

此代码交织起始于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);
}

Answer 5:

下面的代码查找3张10位的输入数的莫顿数。它采用爱迪从你的链接，并进行位中的步骤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是不是2的力量。

......................9876543210
............98765..........43210
........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 6:

我把上面的，并修改它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 7:

以下是代码片段，以产生3-d点大小为64个比特的莫顿键。

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:

这里有一个发电机，我在Ruby中做出用于生产任意长度的编码方法：

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

文章来源: How to compute a 3D Morton number (interleave the bits of 3 ints)