that the orbits are indeed disjoint:
def lsb(i): return i & (-i)
def U(i): return i + lsb(i)
def Q(i): return i - lsb(i)
def orbit(f, i):
s = set()
while i not in s and i > 0 and i < 64:
s.add(i); i = f(i)
if __name__ == "__main__":
for q in range(1, 16):
for u in range(1, 16):
qo = orbit(Q, q); uo = orbit(U, u)
c = qo.intersection(uo)
print("q:%4s | u:%4s | qo: %20s | uo: %20s | qu: %4s" %
(q, u, qo, uo, c))
§ Case 1:
We note that always decreases the value of , and always increases
it. Hence, if , they meet at this point, and
Hence, they meet exactly once as required.
§ Case 2:
As noted above, always decreases and always increases, hence in this
case they will never meet as required.
§ Case 3:
Let the entire array have size .
Let , where
may be empty strings.
Notice that will always strip away rightmost ones in ,
leading to at some point.
Similarly, will keep on adding new rightmost ones, causing the
state to be .
Hence, at some point .