Задание №5

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Если в двоичной записи числа N нулей больше, чем единиц, то самый левый ноль заменяется на единицу. В противном случае самая правая единица заменяется на ноль.
3. Результат переводится в десятичную систему счисления.
4. Результатом работы алгоритма становится модуль разности исходного числа N и числа, полученного на предыдущем шаге.
Пример 1. Дано число N = 17. Алгоритм работает следующим образом.
1. Строим двоичную запись числа N: 1710 = 100012.
2. В полученном двоичном числе нулей больше, заменяем самый левый ноль: 10001 → 11001.
3. Переводим в десятичную систему: 110012 = 2510.
4. Вычисляем модуль разности: | 17 – 25 | = 8.
Пример 2. Дано число N = 28. Алгоритм работает следующим образом.
1. Строим двоичную запись числа N: 2810 = 111002.
2. В полученном двоичном числе нулей не больше, заменяем самую правую единицу: 11100 → 11000.
3. Переводим в десятичную систему: 110002 = 2410.
4. Вычисляем модуль разности: | 28 – 24 | = 4.
Результат работы алгоритма R = 4.
При каком наименьшем N, не превышающем 109, в результате работы алгоритма получится наибольшее значение R?