python - 32 ビット、64 ビット、および 128 ビットのインターリーブ ビット パターン (モートン キー) を生成します。

Question

32bit用、64bit用、128bit用のモートンキーを最適なコードで作りたい！解決策は何ですか？

Answer 1

Pythonスクリプトを使用した私のソリューションは次のとおりです。

私は彼のコメントからヒントを得ました: Fabian “ryg” Giesen
以下の長いコメントを読んでください! どのビットがどこまで進む必要があるかを追跡する必要があります。
次に、各ステップで、これらのビットを選択して移動し、ビットマスク (最後の行のコメントを参照) を適用してマスクします!

10 ビットの数値と 2 つのインターリーブ ビット (32 ビットの場合) に対する Python スクリプト (以下を参照) のビット マスク ビルダー出力:

Bit Distances: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
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]

Current Mask:           0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 1111 1111
Which bits to shift:    0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000  hex: 0x300
Shifted part (<< 16):   0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 0000 0000  hex: 0x3000000
NonShifted Part:        0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111  hex: 0xff
Bitmask is now :        0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 1111 1111  hex: 0x30000ff
 (this is : bitMask = shifted | nonshifted) 


Current Mask:           0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 1111 1111
Which bits to shift:    0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 0000  hex: 0xf0
Shifted part (<< 8):    0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 0000 0000 0000  hex: 0xf000
NonShifted Part:        0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 0000 1111  hex: 0x300000f
Bitmask is now :        0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 1111 0000 0000 1111  hex: 0x300f00f
 (this is : bitMask = shifted | nonshifted) 


Current Mask:           0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 1111 0000 0000 1111
Which bits to shift:    0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1100 0000 0000 1100  hex: 0xc00c
Shifted part (<< 4):    0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1100 0000 0000 1100 0000  hex: 0xc00c0
NonShifted Part:        0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0011 0000 0000 0011  hex: 0x3003003
Bitmask is now :        0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 1100 0011 0000 1100 0011  hex: 0x30c30c3
 (this is : bitMask = shifted | nonshifted) 


Current Mask:           0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 0000 1100 0011 0000 1100 0011
Which bits to shift:    0000 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000 1000 0010 0000 1000 0010  hex: 0x2082082
Shifted part (<< 2):    0000 0000 0000 0000 0000 0000 0000 0000 0000 1000 0010 0000 1000 0010 0000 1000  hex: 0x8208208
NonShifted Part:        0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 0100 0001 0000 0100 0001  hex: 0x1041041
Bitmask is now :        0000 0000 0000 0000 0000 0000 0000 0000 0000 1001 0010 0100 1001 0010 0100 1001  hex: 0x9249249
 (this is : bitMask = shifted | nonshifted) 

x &= 0x3ff
x = (x | (x << 16)) & 0x30000ff
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 スクリプト!!!

import random;

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,64,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 = list(range(numberOfBits));
    print("BitPositions: " + str(bitPositions))
    maskOld = (1 << numberOfBits) -1

    codeString = "x &= " + hex(maskOld) + "\n"
    for idx in range(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("\nCurrent Mask:\t\t" + binStr(maskOld))
           print("Which bits to shift:\t" + binStr(shifted) + "\t hex: " + hex(shifted))
           shifted = shifted << 2**idx
           print("Shifted part (<< " + str(2**idx) + "):\t" + binStr(shifted)+ "\t hex: " + hex(shifted))

           print("NonShifted Part:\t" + binStr(nonshifted) + "\t hex: " + hex(nonshifted))
           maskNew =  shifted | nonshifted
           print("Bitmask is now :\t" + binStr(maskNew) + "\t hex: " + hex(maskNew) +"\n (this is : bitMask = shifted | nonshifted) \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):
    l=locals();
    exec(codeString,None,l)
    return l['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 = int(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!!!!")