Підрахунок одиниць

Карл — найщасливіша дитина у світі: він сьогодні вранці дізнався, що таке двійкова система числення. Він, наприклад, дізнався, що бінарне представлення додатного числа $k$ — це рядок a_n a_{n-1} \ldots a_1 a_0, де кожне a_i — цифра $0$ або $1$, причому a_n = 1:

Дуже цікаво спостерігати, як він перетворює десяткові числа на двійкові, а також складає і множить їх.

Цезар — старший брат Карла, і він не може просто так спостерігати за щастям брата. Тому він приготував завдання: «Поглянь, Карле, у мене до тебе питання: я дам тобі два цілих числа $a$ і $b$, а ти скажеш мені, скільки одиниць міститься у двійковому представленні всіх цілих чисел від $a$ до $b$ включно. Готуйся». Карл погодився прийняти виклик. За кілька хвилин він повернувся зі списком двійкових представлень усіх чисел від $1$ до $100$. «Цезаре, я готовий». Цезар усміхнувся і сказав: «Добре, я вибираю a = 10^{15} і b = 10^{16}. Твій список марний».

Карл не хоче програти братові, йому потрібно швидке рішення. Чи можете ви йому допомогти?