Kiểm tra số Bleak (số u ám) trong C++

Số Bleak: Không thể viết dưới dạng x + count_set_bits(x) với x ≥ 0. Nếu tồn tại x thỏa mãn → không phải Bleak.

Ví dụ: 3 = 2 + count_bits(2) = 2+1 → không Bleak. 4 không thể biểu diễn → Bleak.

Giải thuật

Duyệt x từ 1 đến n-1. Nếu x + count_bits(x) == n → trả về false. Nếu hết vòng lặp → true.

Ví dụ minh họa

#include <iostream>
using namespace std;

int countSetBits(int x) {
    unsigned int count = 0;
    while (x) {
        x &= (x - 1); // xoa bit 1 cuoi cung
        count++;
    }
    return count;
}

bool isBleak(int n) {
    for (int i = 1; i < n; i++)
        if (i + countSetBits(i) == n)
            return false;
    return true;
}

int main() {
    cout << (isBleak(3) ? "Bleak" : "Khong Bleak") << endl; // No
    cout << (isBleak(4) ? "Bleak" : "Khong Bleak") << endl; // Yes
}

Kết quả

Khong Bleak
Bleak