python - 讲解Z阶曲线的代码

Question

在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)还是？

Answer 1

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