查找将一个节点划分为4个节点的位位置

2024-05-15 • 问答

我有一个根节点（S1），其范围值表示为1073741824（最小），2147483648（最大）。我将该范围划分为代表4个新生成的节点的4个相等范围。子节点的范围分别为（S2）1073741824（最小），1342177280（最大）;（S3）1342177280（最小），1610612736（最大） ; （S4）1610612736（最小值），1879048192（最大值）;（S5）1879048192（min），2147483648（最大值）。所有数字的长度均为32位。附图可以更清楚地说明：

  (S1) 1073741824 (min),2147483648 (max)
  (S2) 1073741824 (min),1342177280 (max)
  (S3) 1342177280 (min),1610612736 (max)
  (S4) 1610612736 (min),1879048192 (max)
  (S5) 1879048192 (min),2147483648 (max)

  [Spawning 4 nodes from one node][1]

在二进制中，边界是

S1 min = S2 min = 1073741824 = 01000000000000000000000000000000_bin
S2 max = S3 min = 1342177280 = 01010000000000000000000000000000_bin
S3 max = S4 min = 1610612736 = 01100000000000000000000000000000_bin
S4 max = S5 min = 1879048192 = 01110000000000000000000000000000_bin
S5 max = S1 max = 2147483648 = 10000000000000000000000000000000_bin

因此，如果数字以二进制表示，则有什么方法可以找到将原始范围（1073741824（最小值），2147483648（最大值））分为4个相等的位位置（从第0位位置到第31位位置）大小的团体？有什么算法可以做到吗？例如我想找到'i'，'j'位的位置（0

总体思想……

S2，S3，S4，S5的支化作用可以表示为ij = 00,01,10,11

...对我来说似乎是过早的优化。特别是由于您使用的是python，因此开始时并不那么快。但是，如果您出于其他原因想要提取这些位，则这是一种方法。请记住，在您的示例中两位还不够。

可以通过简单的方法计算所有边界，然后将它们组合在一起，从而只保留变化的位，从而找出要修改的位。

#! /usr/bin/python3
min = 1073741824
max = 2147483648

# divide in the straight-forward way
diff = max - min
bounds = [min + i*diff//4 for i in range(5)]

# combine bounds such that only the changing bits remain set
changingBits = 0
for x in bounds:
    for y in bounds:
        changingBits |= x ^ y

print('bounds:')
for b in bounds:
    print('{0:010d} {0:032b}'.format(b))
print()
print('changing bits:')
print(' '*11 +  '{0:032b}'.format(changingBits))

这将打印

bounds:
1073741824 01000000000000000000000000000000
1342177280 01010000000000000000000000000000
1610612736 01100000000000000000000000000000
1879048192 01110000000000000000000000000000
2147483648 10000000000000000000000000000000

changing bits:
           11110000000000000000000000000000

请注意，对于任意数字min和max，您可以获取非连续的更改位。这是min=3和max=82589933的示例。

bounds:
0000000003 00000000000000000000000000000011
0020647485 00000001001110110000111000111101
0041294968 00000010011101100001110001111000
0061942450 00000011101100010010101010110010
0082589933 00000100111011000011100011101101

changing bits:
           00000111111111110011111011111111

查找将一个节点划分为4个节点的位位置

chieiey2009 回答：查找将一个节点划分为4个节点的位位置

大家都在问