Двоичное число
Планета Шелезяка... Полезных ископаемых на планете нет. Воды тоже нет. Атмосферы нет. Ничего на планете нет. Если что и было, роботы все истратили и живут в бедности.
Кир Булычев "Путешествие Алисы"
Как известно, планета Шелезяка расположена в отдаленной части нашей Галактики, в стороне от космических трасс. Воду роботы (единственные обитатели планеты во второй половине 21-го века) ликвидировали специально, чтобы не ржаветь (они опасались ливней и наводнений). В связи с этим планета оказалась решительно никому кроме роботов не нужна.
Однажды на пустынную планету прилетели пираты. То были настоящие матерые злодеи. Их сердцу была неведома жалость. Они захватили почти всех роботов и увезли их в далекую-далекую галактику и заставили работать на шахтах на планете Бендомир.
Прошло немало времени, прежде чем про это стало известно на Земле. Ричард Темпест, бесстрашный сотрудник института Времени, отправился в прошлое с целью помешать дьявольским планам пиратов. Как оказалось, пользуясь гостеприимством роботов, пираты предлагали роботам решить задачку на скорость. Однако вычислительные возможности роботов были не велики, а оптимизировать алгоритмы их работы было некому. Поэтому все, что оставалось злодеям — загрузить в трюм корабля бесчувственные тела роботов, поглощенных вычислениями.
Ричарду удалось узнать, над чем безуспешно бились электронные мозги роботов. Пираты предлагали им целое неотрицательное число n. После этого они просили узнать, что произойдет с этим числом, если к нему n раз применить операцию: взять старший бит в двоичной записи числа и поставить его в конец. Например, если один раз применить эту операцию к числу 14_10 = 1110_2, получится 13_10 = 1101_2. После повторного применения получится 11_10 = 1011_2.
Ричард присвистнул. Если ему удастся раздобыть программу, которая быстро решает эту задачу, он сможет отправиться во времена до прилета пиратов и загрузить в роботов эту программу, чтобы они смогли противостоять злобным пиратам.
Вы - сотрудник института Времени, которому поручено в срочном порядке написать эту программу. Помогите спасти роботов.
Входные данные
Целое число n (0 ≤ n ≤ 10^18).
Выходные данные
Выведите ответ на задачу, поставленную пиратами перед роботами.