from random import randint
from math import log, ceil
"""
Používané bitové operátory:
 - Bitový posun doleva (x << c): posune číslo x v binární reprezentaci o c míst
   doleva, tedy efektivně x vynásobí 2 ** c
 - Bitový posun doprava (x >> c): to samé, ale posouváme doleva / celočíselně
   dělíme 2 ** c
 - Bitový AND (a & b): Výsledek bude mít jedničky na těch místech, kde mají
   jedničky obě čísla. Dá se na to taky dívat tak, že z čísla a necháme zapnuté
   jen některé bity, které si vybereme pomocí čísla b.
"""


def kth_bit(x, k):
    # vrátí k-tý nejpravější bit čísla x (indexujeme od 0)
    return (x >> k) & 1;
    # nejprve si k-tý bit posuneme na nulté místo a pak pomocí ANDu vybereme
    # jen jej.


def popcount(x):
    # vrátí počet jedničkových bitů v x
    s = 0
    while x > 0:
        s += x & 1
        x >>= 1
    return s


def equal(A, B, N, repeats=1):
    for i in range(repeats):
        if not _equal(A, B, N):
            return False
    return True # vrátíme True, právě když uspějou všechny testy


def _equal(A, B, N):
    mask = randint(0, 2 ** N - 1)
    # Předpokládáme-li, že randint generuje čísla rovnoměrně náhodně, pak i
    # jejich odpovídající N-bitové posloupnosti jsou rovnoměrně náhodné

    Am = A & mask
    Bm = B & mask
    A_parity = popcount(Am) % 2
    B_parity = popcount(Bm) % 2
    # Necháme Alici a Boba, aby si poslali A_parity a B_parity
    return A_parity == B_parity


def binsearch_answer(A, B, N):
    # Hledáme první pozici, kde se čísla neshodují
    def topbits(A, c):
        # vrátí nejlevějších c bitů čísla A
        return A >> (N - c)

    amount = ceil(log(log(N, 2), 2) + 2) # Zaokrouhlíme nahoru
    l, r = 0, N
    best_result = N + 1
    while l <= r:
        c = (l + r) // 2
        Ac = topbits(A, c)
        Bc = topbits(B, c)
        if equal(Ac, Bc, c, amount):
            l = c + 1
        else:
            best_result = c
            r = c - 1

    if best_result == N + 1:
        print("Čísla jsou stejná.")
    else:
        pos = N - best_result # Nesmíme zapomenout, že jsme binárně hledali zleva, ale bity číslujeme zprava
        a = kth_bit(A, pos)
        b = kth_bit(B, pos)
        print("A < B" if a < b else "A > B")


A = 105
B = 108
N = 8 # 2 ** 8 = 256
binsearch_answer(A, B, N)