Chương trình Python đếm số bit 1 (set bits) trong số nguyên

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho số nguyên n, cần đếm số bit 1 trong biểu diễn nhị phân của số đó.

Hãy quan sát giải pháp trong triển khai dưới đây:

# Cách tiếp cận đơn giản (naive)

Ví dụ 1

# đếm bit
def count(n):
    count = 0
    while (n):
        count += n & 1
        n >>= 1
    return count

# main
n = 15
print("Số bit 1:", count(n))

Kết quả

Số bit 1: 4

# Cách đệ quy

Ví dụ 2

# đệ quy
def count(n):
    # base case
    if (n == 0):
        return 0
    else:
        # bit cuối có set không
        return (n & 1) + count(n >> 1)

# main
n = 15
print("Số bit 1:", count(n))

Kết quả

Số bit 1: 4

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python đếm số bit set trong một số nguyên.