Số nguyên có số bit 1 lẻ trong C++

Cho n, đếm số nguyên từ 1 đến n có số bit 1 (set bits) lẻ trong biểu diễn nhị phân.

Ví dụ: n=10 → 5 số.

Giải thuật

• Hàm getSetBitsCount(n): đếm bit 1 bằng n%2 và n/=2
• Hàm getOddSetBitsIntegerCount(n): duyệt 1..n, nếu getSetBitsCount(i)%2==1 thì count++
• Trả về count

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

int getSetBitsCount(int n) { 
    int count = 0; 
    while (n) { 
        if (n % 2 == 1) count += 1; 
        n /= 2; 
    } 
    return count; 
} 

int getOddSetBitsIntegerCount(int n) { 
    int count = 0; 
    for (int i = 1; i <= n; i++) { 
        if (getSetBitsCount(i) % 2 == 1) count += 1; 
    } 
    return count; 
} 

int main() { 
    int n = 10; 
    cout << getOddSetBitsIntegerCount(n) << endl; 
    return 0; 
} 

Đầu ra

5