นับ Bit ที่เป็น 1 (Set Bits / Population Count) ใน Python

โจทย์: นับจำนวนบิต 1 ในการแทนค่า Binary ของจำนวนเต็ม n

วิธีที่ 1: Naive Loop (Bitwise)

def count_bits(n):
    count = 0
    while n:
        count += n & 1      # เช็ค LSB
        n >>= 1             # Shift right
    return count

print(count_bits(15))  # 1111₂ → 4

วิธีที่ 2: Recursive

def count_bits(n):
    if n == 0:
        return 0
    return (n & 1) + count_bits(n >> 1)

print(count_bits(15))  # 4

วิธีที่ 3: Brian Kernighan's Algorithm (เร็วที่สุด)

n & (n-1) ลบบิต 1 ตัวสุดท้ายออกทุกครั้ง

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

วิธีที่ 4: Built-in (Python 3.8+)

print((15).bit_count())  # 4
print(bin(15).count('1'))  # ทุก Version

ผลลัพธ์

The number of bits: 4

เปรียบเทียบ