Đếm Bit

Cho số nguyên $n$, hãy đếm tổng số bit 1 trong biểu diễn nhị phân của tất cả các số nguyên từ $1$ đến $n$.

Dữ liệu vào

Một số nguyên $n$.

Dữ liệu ra

Tổng số bit 1.

Ràng buộc

• $1\le n\le {10}^{15}$

Ví dụ