Đếm số 1 trong biểu diễn nhị phân

Bối cảnh

Một số nguyên không âm được biểu diễn ở hệ nhị phân. Bạn cần đếm số bit 1 bằng recursion mà không dùng thư viện bitset.

Mỗi bước, n%2 cho bit cuối và n/2 bỏ bit đó.

Yêu cầu

1. Viết hàm đệ quy đếm số bit 1.
2. Base case n=0 trả 0.
3. Recursive case cộng n%2 với kết quả của n/2.
4. In kết quả.

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

Bắt buộc dùng recursion; không dùng bitset, popcount hoặc STL.

Online Judge chủ yếu chấm output. Giảng viên sẽ quan sát thêm cách tổ chức hàm khi review code để bảo đảm học viên luyện đúng kỹ năng của buổi.

Input

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

Output

Một số nguyên.

Ràng buộc

0 ≤ n ≤ 10^18.

Ví dụ 1

Input

0

Output

0

Giải thích

0 có biểu diễn nhị phân chỉ gồm các bit 0 nên số bit 1 bằng 0.

Ví dụ 2

Input

1

Output

1

Giải thích

1 có đúng một bit 1 nên kết quả là 1.

Thông tin học tập

• Module: M04
• Buổi: B13
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: recursion, binary decomposition, modulo, integer division, base case
• Giới hạn kiến thức: B01-B13
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100