Chương trình Python đếm tổng bit set từ 1 đến n

Cho số nguyên dương n, chuyển sang biểu diễn nhị phân và đếm tổng số bit set (bit 1).

Ví dụ

Input: n=3
Output: 4

Thuật toán

Bước 1: Nhập số nguyên dương.
Bước 2: Chuyển sang nhị phân.
Bước 3: Khởi tạo biến s = 0.
Bước 4: Duyệt từng phần tử và cộng dồn.
Bước 5: Hiển thị tổng.

Ví dụ mã

# Chương trình Python đếm set bits từ 1 đến n
def countbits(n):
    # Khởi tạo counter
    c = 0
    for i in range(1, n + 1):
        c += bitsetcount(i)
    return c

def bitsetcount(x):
    if (x <= 0):
        return 0
    return (0 if int(x % 2) == 0 else 1) + bitsetcount(int(x / 2))

# Driver program
n = int(input("Enter the value of n"))
print("Total set bit count is", countbits(n))

Kết quả

Enter the value of n10
Total set bit count is 17