Ikki sonining darajalari bo'yicha binar qidiruv

G‘oya (eng sodda)

Biz javobni bitlar bo‘yicha, eng kattasidan boshlab quramiz. Har bir qadamda savol beramiz:

«Joriy javobga $2^k$ ni qo‘shsa bo‘ladimi?»

Agar bo‘lsa — qo‘shamiz, bo‘lmasa — kichikroq qadamga o‘tamiz. Aslida, biz javob bitlarini kattasidan kichigiga qarab ko‘rib chiqamiz.

long long ans = 0;

for (int i = 60; i >= 0; i--) {
    if (check(ans + (1ll << i))) {
        ans += (1ll << i);
    }
}