Binary search by powers of two

Idea (the simplest)

We build the answer bit by bit, starting from the largest. At each step we ask the question:

“Is it possible to add $2^k$ to the current answer?”

If it is possible — we add it, if not — we move on to a smaller step. Essentially, we iterate over the bits of the answer from the most significant to the least significant.

Template

long long ans = 0;

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