Этот-то бит 1, а остальные как определить?

То, что это работает легко показать по индукции. Берем старший бит чисел на отрезке (пусть 2^k). Если на этом отрезке есть число 2^k-1, то ясно что надо брать пару (2^k-1,2^k). Иначе вычтем из всех чисел отрезка 2^k и перейдем к меньшему отрезку.

За O(1) не знаю, но на O(log(r)) можно. Просто идти по битам, начиная со старшего и действовать аналогично тому, что выше написано.

Киньте ссылку на условие, пожалуйста.