Задание 5 ЕГЭ, информатика: Посимвольное двоичное преобразование

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.

1.  Строится двоичная запись числа N.

2.  Если в двоичной записи числа N нулей больше, чем единиц, то самый левый ноль заменяется на единицу. В противном случае самая правая единица заменяется на ноль.

3.  Результат переводится в десятичную систему счисления.

4.  Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге.

Пример 1. Дано число N  =  17. Алгоритм работает следующим образом.

1.  Строим двоичную запись числа N: 17₁₀  =  10001₂.

2.  В полученном двоичном числе нулей больше, заменяем самый левый ноль: 10001 → 11001.

3.  Переводим в десятичную систему: 11001₂  =  25₁₀.

4.  Вычисляем модуль разности: |17 − 25|  =  8.

Пример 2. Дано число N  =  28. Алгоритм работает следующим образом.

1.  Строим двоичную запись числа N: 28₁₀  =  11100₂.

2.  В полученном двоичном числе нулей не больше, заменяем самую правую

единицу: 11100 → 11000.

3.  Переводим в десятичную систему: 11000₂  =  24₁₀.

4.  Вычисляем модуль разности: |28 − 24|  =  4.

Результат работы алгоритма R  =  4.

При каком наименьшем N, не превышающем 10⁹, в результате работы алгоритма получится наибольшее значение R?