def comparator(x):
    """Comparator function: input consists of two n-bit numbers. Output is
    0 if the first is larger or equal, or 1 if the second is larger."""
    assert len(x) % 2 == 0
    n = len(x) // 2
    # no need to convert from binary. just use list comparison
    return x[:n] < x[n:]