Kiểm tra lũy thừa của 2 và Đếm số bit 1 (Hamming Weight)
Trong hệ thống mã hóa và kiến trúc máy tính của AI Empire Academy, các thanh ghi và mặt nạ bit (bitmask) đóng vai trò tối ưu hóa bộ nhớ.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python basics, loops.
Nội dung đề bài
Mục tiêu kiến thức
- Nắm vững các phép toán thao tác trên bit (
&,|,^,>>,<<). - Áp dụng kỹ thuật kiểm tra lũy thừa của 2 trong thời gian O(1) bằng tính chất
n & (n - 1) == 0. - Triển khai thuật toán Brian Kernighan để đếm số bit 1 (Hamming Weight / Popcount) hiệu quả.
Mô tả bài toán
Trong hệ thống mã hóa và kiến trúc máy tính của AI Empire Academy, các thanh ghi và mặt nạ bit (bitmask) đóng vai trò tối ưu hóa bộ nhớ.
Bạn hãy viết hàm power_of_two_and_popcount(n: int) -> tuple[bool, int] thực hiện hai nhiệm vụ:
- Xác định số nguyên n có phải là một lũy thừa nguyên dương của 2 (2k với k ≥ 0) hay không. Lưu ý: các số ≤ 0 không phải là lũy thừa của 2.
- Đếm số lượng bit 1 (Hamming weight / popcount) trong biểu diễn nhị phân của giá trị tuyệt đối |n|.
Input
- Tham số:
n(số nguyênint, có thể âm, bằng 0 hoặc rất lớn).
Output
- Trả về: Một
tuple[bool, int]gồm: is_power_of_two:Truenếu n > 0 và là lũy thừa của 2, ngược lạiFalse.popcount: số lượng bit 1 trong biểu diễn nhị phân của |n|.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.
Ví dụ 1
Input
power_of_two_and_popcount(16)Output
[True, 1]Giải thích
Hàm được gọi với các tham số mẫu trên và trả về kết quả chính xác theo yêu cầu.
Ví dụ 2
Input
power_of_two_and_popcount(0)Output
[False, 0]Giải thích
Hàm được gọi với bộ tham số thứ hai và trả về kết quả tương ứng theo thiết kế.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.