Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def z(x0, y0):
- out = []
- x = (x0 << 1)
- y = (y0 << 1)
- n = 1
- other = lambda t: t ^ (n << 1)
- parent = lambda t: (t | n) & ~(n << 1)
- b = False # whether some descendant of x is greater than x0
- c = (x == y)
- while n <= x0:
- nx, x, ny, y = other(x), parent(x), other(y), parent(y)
- if c:
- # after x and y meet on their path to the root
- if nx < x:
- out.append(nx)
- elif x == y:
- # they meet for the first time
- if not b:
- out.append(other(nx))
- c = True
- else:
- # x and y have not met yet
- if not b and x < nx:
- b = True
- out.append(other(nx))
- elif b and nx < x:
- out.append(nx)
- out.append(ny)
- n <<= 1
- return sorted(out)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement