Tổng số bit 1 từ 0 đến N

Bối cảnh

Một hệ thống nén dữ liệu lưu các số nguyên từ 0 đến N dưới dạng nhị phân và cần ước lượng tổng số bit 1 xuất hiện trong toàn bộ tập đó. Ví dụ, với N=3, các biểu diễn là 0, 1, 10, 11; tổng số bit 1 là 0+1+1+2 = 4. Nếu N lên tới 10^12, việc duyệt từng số rồi đếm bit là quá chậm.

Bạn cần xây dựng một lời giải đệ quy dựa trên cấu trúc của các khối nhị phân. Với x = 2^k là lũy thừa của 2 lớn nhất không vượt N, các số từ 0 đến x-1 tạo thành một khối hoàn chỉnh k bit. Trong khối này, mỗi vị trí bit bật đúng một nửa số lần, nên tổng số bit 1 là k*x/2. Các số từ x đến N đều có bit cao nhất bằng 1, đóng góp thêm N-x+1, còn phần bit thấp của chúng tương ứng đúng với các số từ 0 đến N-x. Từ quan sát đó, bài toán tự thu nhỏ thành một lời gọi cùng loại với N-x.

Đây là bài Advanced theo phong cách HSG/ICPC: khó nằm ở việc tìm recurrence toán học, không phải ở cú pháp C++.

Khi làm bài, không nên bắt đầu bằng cách viết recursion ngay. Hãy thử liệt kê tổng số bit 1 ở các mốc 1, 3, 7, 15 để nhận ra các khối 0..2^k-1. Mỗi khối hoàn chỉnh có quy luật rất đều, còn phần dư sau mốc lũy thừa của 2 lại chính là một bài toán nhỏ hơn cùng loại. Việc phát hiện hai lớp cấu trúc này là bước suy luận quan trọng nhất; code chỉ là bước hiện thực recurrence sau khi mô hình toán học đã rõ.

Yêu cầu

1. Đọc N.
2. Tìm lũy thừa 2 lớn nhất x=2^k ≤ N bằng hàm đệ quy.
3. Dùng recurrence để tính tổng số bit 1 trong mọi số từ 0 đến N.
4. Không duyệt từng số từ 0 đến N.
5. In kết quả.

Yêu cầu tổ chức code

Bắt buộc dùng recurrence đệ quy; không dùng bitset/popcount để duyệt từng số.

Online Judge chấm output. Giảng viên có thể review source code để xác nhận học viên dùng đúng recursion và không vượt prerequisite.

Input

Một số nguyên không âm N.

Output

Một số nguyên: tổng số bit 1 trong các biểu diễn nhị phân của mọi số từ 0 đến N.

Ràng buộc

0 ≤ N ≤ 10^12.

Ví dụ 1

Input

0

Output

0

Giải thích

Với N=0, tập cần xét chỉ có số 0. Biểu diễn nhị phân của 0 không chứa bit 1 nào nên tổng bằng 0. Hàm cũng chạm base case ngay, không cần tìm lũy thừa 2 hay tạo recursive call khác. Vì vậy output là 0.

Ví dụ 2

Input

1

Output

1

Giải thích

Với N=1, lũy thừa 2 lớn nhất không vượt N là x=1=2^0. Khối hoàn chỉnh trước x chỉ có số 0 nên đóng góp 0 bit 1. Từ x đến N chỉ có số 1, bit cao nhất đóng góp 1-1+1 = 1. Phần dư là N-x=0, nên recursive call còn lại trả 0. Tổng cuối là 0+1+0 = 1.

Thông tin học tập

• Module: M04
• Buổi: B13
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: recursion, binary decomposition, highest power of two, recursive counting, mathematical recurrence
• Giới hạn kiến thức: B01-B13
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100