python — создание чередующихся битовых комбинаций (ключей Morton) для 32-битных, 64-битных и 128-битных
Я хочу создать ключ для 32-битных, 64-битных и 128-битных ключей с оптимальным кодом!
Какое решение?
Решение
Вот мое решение с помощью скрипта Python:
Я понял намек на его комментарий: Фабианский «рыг» Гизен
Прочитайте длинный комментарий ниже! Нам нужно отслеживать, какие биты должны идти, как далеко!
Затем на каждом шаге мы выбираем эти биты, перемещаем их и применяем битовую маску (см. Комментарий в последних строках), чтобы маскировать их!
Вывод построителя битовой маски скрипта 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
А для 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 codeStringnumberOfBits = 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!!!!")
Другие решения
Других решений пока нет …