它如何获得相同的前缀和后缀?
How it is getting the same prefix and suffix?
我看到了这段代码 here,我想知道下面的代码是如何工作的。我理解其中的逻辑,但只是想知道实现是如何使用 nice bit 逻辑的。
我已经修改了代码使其适用于 4 位。我想知道如何检测到公共前缀,即在下面的情况 5 中?第 12 行和第 13 行背后的数学推理是什么?
1 import random
2 #suppose the range of number is 8 bits
3 #and we are working with 4bits prefix
4 #and 4bits suffix
5 data = []
6 bits = 4
7 for i in range(100000):
8 data.append(random.randint(0, 100))
9 suffix = 5
10 for i in data:
11 i = int(i)
12 s = i^(suffix<<bits)
13 if s < (1 << bits):
14 print("s is ", s, "prefix of", i, "is", s, "and suffix is ", suffix)
bits == 4
prefix == 5 == 00000101
prefix << bits == 01010000
suffix = i XOR 01010000
=> e.g. if i == 0101xxxx => suffix == 0000xxxx (correct prefix)
=> e.g. if i == 1110xxxx => suffix == 1011xxxx (wrong prefix)
1 << bits == 00010000
if (suffix < 00010000) ~ if (suffix is like 0000xxxx) ~ if (i is like 0101xxxx)
因此每个随机数都与前缀进行异或;然后使用它来检查哪些数字具有正确的前缀(如果前 4 位现在是 0000)并获取后缀(最后 4 位)。
我看到了这段代码 here,我想知道下面的代码是如何工作的。我理解其中的逻辑,但只是想知道实现是如何使用 nice bit 逻辑的。
我已经修改了代码使其适用于 4 位。我想知道如何检测到公共前缀,即在下面的情况 5 中?第 12 行和第 13 行背后的数学推理是什么?
1 import random
2 #suppose the range of number is 8 bits
3 #and we are working with 4bits prefix
4 #and 4bits suffix
5 data = []
6 bits = 4
7 for i in range(100000):
8 data.append(random.randint(0, 100))
9 suffix = 5
10 for i in data:
11 i = int(i)
12 s = i^(suffix<<bits)
13 if s < (1 << bits):
14 print("s is ", s, "prefix of", i, "is", s, "and suffix is ", suffix)
bits == 4
prefix == 5 == 00000101
prefix << bits == 01010000
suffix = i XOR 01010000
=> e.g. if i == 0101xxxx => suffix == 0000xxxx (correct prefix)
=> e.g. if i == 1110xxxx => suffix == 1011xxxx (wrong prefix)
1 << bits == 00010000
if (suffix < 00010000) ~ if (suffix is like 0000xxxx) ~ if (i is like 0101xxxx)
因此每个随机数都与前缀进行异或;然后使用它来检查哪些数字具有正确的前缀(如果前 4 位现在是 0000)并获取后缀(最后 4 位)。