โปรแกรม Python นับ set bits ทั้งหมดจาก 1 ถึง n

นับจำนวน bit 1 (set bits) ในการแสดงผล binary ของทุกตัวเลขจาก 1 ถึง n

ตัวอย่าง

n=3 -> binary: 1, 10, 11 -> set bits: 1+1+2 = 4

อัลกอริทึม

1. ฟังก์ชัน bitsetcount(x) เรียก recursive นับ bit 1
2. วนลูป 1 ถึง n สะสมผลรวม

โค้ดตัวอย่าง

def countbits(n):
    c = 0
    for i in range(1, n+1):
        c += bitsetcount(i)
    return c

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

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

ผลลัพธ์

Enter the value of n: 10
Total set bit count is 17