爲32位，64位和128位生成交織位模式（morton密鑰）

Question

我想爲32位和64位和128位生成一個密鑰，並使用最優代碼！ 什麼是解決方案？

Answer 1

這裏是我的解決方案與Python腳本：

我心領神會從他的評論：Fabian 「ryg」 Giesen
閱讀下面的長註釋！我們需要跟蹤哪些位需要走多遠！
然後在每一步中，我們選擇這些位並移動它們並應用一個位掩碼（參見注釋最後一行）來掩蓋它們！ Python腳本的

位掩碼生成器輸出（見下文），用於一個10位數字和2個交織比特（32位）：

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 

而對於一個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製作和檢查交織模式的腳本！

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