eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Подсчет единиц

Подсчет единиц

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Карл — самый счастливый ребенок в мире: он сегодня утром узнал, что такое двоичная система счисления. Он например узнал, что бинарное представление положительного числа k есть строка a_na_{n-1} ... a_1a_0, где каждое a_i — цифра 0 или 1, начиная с a_n = 1, при этом

Очень интересно наблюдать превращение десятичных чисел в двоичные, а также складывать и умножать их.

Цезарь — старший брат Карла, и он не может просто так стоять и наблюдать за счастьем брата. Поэтому он приготовил задачу: "Посмотри, Карл, у меня есть к тебе вопрос: Я дам тебе два целых числа a и b, а ты скажешь мне сколько 1-ц в бинарном представлении всех чисел от a до b включительно. Приготовься". Карл согласился принять вызов. Через несколько минут он вернулся со списком двоичных представлений всех чисел от 1 до 100. "Цезарь, я готов". Цезарь улыбнулся и сказал: "Хорошо, я выберу a = 10^{15} и b = 10^{16}. Твой список бесполезен".

Карл не хочет проиграть брату, ему необходимо быстрое решение. Можете ли ему помочь?

Входные данные

В одной строке расположены два целых числа a и b~(1 \le a \le b \le 10^{16}).

Выходные данные

Выведите общее количество цифр 1 в двоичном представлении всех целых чисел от a до b включительно.

Пример

Входные данные #1
2 12
Выходные данные #1
21
Автор Ray Williams Robinson Valiente
Источник 2013 ACM Regional Latino America, Задача C