Advertisement
JoelSjogren

Untitled

Mar 24th, 2020
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.88 KB | None | 0 0
  1. def z(x0, y0):
  2.     out = []
  3.     x = (x0 << 1)
  4.     y = (y0 << 1)
  5.     n = 1
  6.     other = lambda t: t ^ (n << 1)
  7.     parent = lambda t: (t | n) & ~(n << 1)
  8.     b = False  # whether some descendant of x is greater than x0
  9.     c = (x == y)
  10.     while n <= x0:
  11.         nx, x, ny, y = other(x), parent(x), other(y), parent(y)
  12.         if c:
  13.             # after x and y meet on their path to the root
  14.             if nx < x:
  15.                 out.append(nx)
  16.         elif x == y:
  17.             # they meet for the first time
  18.             if not b:
  19.                 out.append(other(nx))
  20.             c = True      
  21.         else:
  22.             # x and y have not met yet
  23.             if not b and x < nx:
  24.                 b = True
  25.                 out.append(other(nx))
  26.             elif b and nx < x:
  27.                 out.append(nx)
  28.             out.append(ny)
  29.         n <<= 1
  30.     return sorted(out)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement