Đếm bit 0 trong khoảng cho trước của số nhị phân trong C++

Giới thiệu

Cho số nguyên và khoảng [left, right] (1-indexed từ bit thấp nhất). Đếm số bit 0 trong khoảng đó của biểu diễn nhị phân.

Ví dụ

• n = 50 (00110010), left=2, right=5 → Các bit: vị trí 2=1, 3=0, 4=0, 5=1 → 2 bit 0
• n = 42 (00101010), left=1, right=6 → 3 bit 0

Ý tưởng giải thuật

1. Tạo mask cho khoảng [left, right]: mask = ((1 << right) - 1) ^ ((1 << (left-1)) - 1)
2. Lấy bits trong khoảng: bits = n & mask
3. Đếm bit 1 trong bits.
4. Bit 0 = (right - left + 1) - bit_1_count.

Ví dụ triển khai (C++)

#include <iostream>
using namespace std;

int countUnsetBitsInRange(int n, int left, int right) {
    // Tạo mask cho bit left..right (1-indexed từ LSB)
    int mask = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);
    int bitsInRange = n & mask;
    
    int setBits = 0;
    int temp = bitsInRange;
    while (temp) {
        setBits += temp & 1;
        temp >>= 1;
    }
    
    int totalBits = right - left + 1;
    return totalBits - setBits;
}

int main() {
    int n = 80, left = 1, right = 4;
    cout << "So bit 0 trong khoang [" << left << "," << right << "]: "
         << countUnsetBitsInRange(n, left, right); // 2
    return 0;
}

Đầu vào

80, left=1, right=4

Đầu ra

2