Chương trình đếm tổng số bit 1 của tất cả các số trong khoảng 0 đến n bằng Python

Giả sử chúng ta có một số num. Với mỗi số i trong khoảng 0 ≤ i ≤ num, chúng ta tính số lượng bit 1 trong biểu diễn nhị phân của chúng và trả về dưới dạng danh sách. Ví dụ, nếu số là 5, các số là [0, 1, 2, 3, 4, 5], số bit 1 tương ứng là [0, 1, 1, 2, 1, 2], tổng cộng là 7.

Quy trình giải quyết

1. Khởi tạo mảng result kích thước num + 1 với toàn giá trị 0.
2. Khởi tạo offset = 0.
3. Với i từ 1 đến num:
   • Nếu i & (i - 1) == 0 (là lũy thừa của 2), gán result[i] = 1 và offset = 0.
   • Ngược lại, tăng offset lên 1 và gán result[i] = 1 + result[offset].
4. Trả về tổng các phần tử của result.

Ví dụ mã nguồn

class Solution:
    def countBits(self, num):
        result = [0] * (num + 1)
        offset = 0
        for i in range(1, num + 1):
            if i & (i - 1) == 0:
                result[i] = 1
                offset = 0
            else:
                offset += 1
                result[i] = 1 + result[offset]
        return sum(result)

ob1 = Solution()
print(ob1.countBits(5))  # Output: 7

Đầu vào

5

Đầu ra

7