Đếm số bit 1 (set bits) trong một khoảng của số nguyên trong Python

Cho số nguyên dương n, chuyển sang nhị phân. Đếm số bit 1 (set bits) trong khoảng vị trí từ l đến r (đếm từ bit thấp nhất là vị trí 1).

Cách 1: Dùng bin() và cắt chuỗi

Chuyển sang nhị phân, bỏ tiền tố '0b', đảo chuỗi để bit thấp nhất ở chỉ số 0. Sau đó đếm các ký tự '1' trong khoảng [l-1, r-1].

Ví dụ

def SetBits_cnt(n, l, r):
    bin_val = bin(n)
    bin_val = bin_val[2:]          # bỏ '0b'
    print(bin_val)
    bin_val = bin_val[-1::-1]      # đảo chuỗi
    print(len([bin_val[i] for i in range(l - 1, r) if bin_val[i] == '1']))

SetBits_cnt(83, 1, 6)

Kết quả

1010011
3

Cách 2: Sử dụng phép bitwise

Tạo mặt nạ (mask) cho khoảng bit từ l đến r: ((1 << r) - 1) ^ ((1 << (l-1)) - 1). Áp dụng AND với n, sau đó đếm bit 1 của kết quả (dùng thuật toán Brian Kernighan).

Ví dụ

def trackBitsInRange(n, l, r):
    bit_num = ((1 << r) - 1) ^ ((1 << (l - 1)) - 1)
    return trackSetBits(n & bit_num)

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

print(trackBitsInRange(83, 1, 6))