Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Đếm bit set trong khoảng trong C++

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

Ví dụ: num=50 (110010), left=2, right=5 → bits 2..5 là 1001 → 2 bit 1.

Giải thuật: Tạo mask cho khoảng [left, right]: mask = ((1<. Kết quả = __builtin_popcount(num & mask).

Ví dụ

#include <iostream>
using namespace std;

unsigned int bits(unsigned int number, unsigned int left, unsigned int right) {
    unsigned int count = 0;
    // Hiển thị 8-bit
    for (unsigned i = 1 << 7; i > 0; i >>= 1)
        cout << ((number & i) ? '1' : '0');
    // Đếm bit trong khoảng
    int mask = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);
    count = __builtin_popcount(number & mask);
    cout << "\nCount: " << count;
    return count;
}

int main() {
    bits(42, 2, 5);
    return 0;
}

Đầu ra

8-bit digits of 42 is: 00101010
Count of total set bits in a range are: 2