Skip to main content
 首页 » 编程设计

python之讲解Z阶曲线的代码

2024年10月25日16emanlee

在Z-order curve的解释中在 Wikipedia , 有一些 Python代码:

def less_msb(x, y): 
    return x < y and x < (x ^ y) 

这里有两个问题:

  1. 什么是 msb的缩写?

  2. 自 x < y ,我为什么要比较x和 (x^y)还是?

请您参考如下方法:

msb是Most Significant Bit

One way to determine whether the most significant smaller is to compare the floor of the base-2 logarithm of each point. It turns out the following operation is equivalent, and only requires exclusive or operations:

def less_msb(x, y): 
   return x < y and x < (x ^ y) 

需要进行第二次比较,因为即使x < y , x的 msb不一定小于 y的 msb :

例如x = 2 , y = 3 : x < y但是x和 y有相同的msb :

print bin(2), bin(3) 
0b10 0b11 

您可以在下表中看到 x^y不小于x直到 y的 bit_length 大于 x的,直到那时他们的 msb s 相等:

(2, 3)   2^3 =  1   bin(2):   10    bin(3):    11 
(2, 4)   2^4 =  6   bin(2):   10    bin(4):   100 
 
(3, 4)   3^4 =  7   bin(3):   11    bin(4):   100 
 
(4, 5)   4^5 =  1   bin(4):  100    bin(5):   101 
(4, 6)   4^6 =  2   bin(4):  100    bin(6):   110 
(4, 7)   4^7 =  3   bin(4):  100    bin(7):   111 
(4, 8)   4^8 = 12   bin(4):  100    bin(8):  1000 
 
(5, 6)   5^6 =  3   bin(5):  101    bin(6):   110 
(5, 7)   5^7 =  2   bin(5):  101    bin(7):   111 
(5, 8)   5^8 = 13   bin(5):  101    bin(8):  1000 
 
(6, 7)   6^7 =  1   bin(6):  110    bin(7):   111 
(6, 8)   6^8 = 14   bin(6):  110    bin(8):  1000 
 
(7, 8)   7^8 = 15   bin(7):  111    bin(8):  1000 
 
(8, 9)   8^9 =  1   bin(8): 1000    bin(9):  1001 
(8,10)  8^10 =  2   bin(8): 1000   bin(10):  1010 
(8,11)  8^11 =  3   bin(8): 1000   bin(11):  1011 
(8,12)  8^12 =  4   bin(8): 1000   bin(12):  1100 
(8,13)  8^13 =  5   bin(8): 1000   bin(13):  1101 
(8,14)  8^14 =  6   bin(8): 1000   bin(14):  1110 
(8,15)  8^15 =  7   bin(8): 1000   bin(15):  1111 
(8,16)  8^16 = 24   bin(8): 1000   bin(16): 10000