Đếm số có đúng 1 bit 1 trong khoảng [0, n] trong C++

Giới thiệu

Cho số n, đếm số nguyên trong [0, n] có đúng 1 bit 1 trong biểu diễn nhị phân (tức là các số là lũy thừa của 2: 1, 2, 4, 8, ...).

Ví dụ

• n = 15 → Các số: 1, 2, 4, 8 → Kết quả: 4
• n = 4 → Các số: 1, 2, 4 → Kết quả: 3

Các cách tiếp cận

Cách 1: Naive - Duyệt và đếm bit (__builtin_popcount)

Duyệt 1..n, đếm số có popcount = 1. O(n log n).

Cách 2: Hiệu quả - Sinh lũy thừa của 2

Khởi tạo temp = 1, khi temp ≤ n: count++, temp *= 2. O(log n).

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

#include <iostream>
using namespace std;

// Cách 1: Naive
int countSingleBitNaive(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++)
        if (__builtin_popcount(i) == 1) count++;
    return count;
}

// Cách 2: Hiệu quả
int countSingleBitFast(int n) {
    int count = 0;
    for (long long p = 1; p <= n; p <<= 1)
        count++;
    return count;
}

int main() {
    int n = 15;
    cout << "Cach 1: " << countSingleBitNaive(n) << endl; // 4
    cout << "Cach 2: " << countSingleBitFast(n) << endl;  // 4
    return 0;
}

Đầu vào

15

Đầu ra

4