นับจำนวนบิต 1 (Set Bits) ในช่วงที่กำหนดของตัวเลข ใน Python

ปัญหา

ให้ตัวเลข n และช่วงบิต l ถึง r (นับจากขวา เริ่มที่ 1) นับจำนวนบิต 1 ในช่วงนั้น

ตัวอย่าง

n = 83 (binary: 1010011), l=1, r=6 → บิต 1-6: 010011 → มี 1 สามบิต → 3

วิธีที่ 1: ใช้ bin() และสไลซ์สตริง

def count_set_bits_range(n, l, r):
    binary = bin(n)[2:][::-1]  # กลับสตริงเพื่อให้ index 0 = บิต 1
    return sum(1 for i in range(l-1, r) if i < len(binary) and binary[i] == '1')

print(count_set_bits_range(83, 1, 6))  # 3

วิธีที่ 2: ใช้ Bitwise Operations (เร็วกว่า)

1. สร้างมาสก์ที่มีบิต 1 เฉพาะช่วง l ถึง r: mask = ((1 << r) - 1) ^ ((1 << (l-1)) - 1)
2. AND กับ n: n & mask
3. นับบิต 1 (Brian Kernighan's algorithm)

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

def count_set_bits_range(n, l, r):
    mask = ((1 << r) - 1) ^ ((1 << (l-1)) - 1)
    return count_set_bits(n & mask)

print(count_set_bits_range(83, 1, 6))  # 3

สรุป

วิธี Bitwise เร็วกว่าและไม่ต้องแปลงสตริง เหมาะสำหรับตัวเลขใหญ่