ตรวจสอบจำนวน Bleak ใน C++

จำนวน Bleak (Bleak Number) คืออะไร?

จำนวน n ที่ ไม่สามารถเขียนในรูป x + countSetBits(x) ได้ สำหรับ x ≥ 1 ใดๆ

โดย countSetBits(x) = จำนวนบิต 1 ในการแสดงไบนารีของ x

ตัวอย่าง

• n = 3: x=1 → 1+1=2, x=2 → 2+1=3 ✓ พบ → ไม่ใช่ Bleak
• n = 4: x=1→2, x=2→3, x=3→3+2=5 ไม่มี x ให้ 4 → เป็น Bleak

อัลกอริทึม

ตรวจสอบ x = 1 ถึง n-1 (เพราะ x + countSetBits(x) ≥ x+1):

bool isBleak(int n) {
    for (int x = 1; x < n; x++) {
        if (x + __builtin_popcount(x) == n)
            return false; // พบ x → ไม่ใช่ Bleak
    }
    return true; // ไม่พบ → เป็น Bleak
}

ตัวอย่างโค้ด C++ ครบถ้วน

#include <iostream>
using namespace std;

int countSetBits(int x) {
    int count = 0;
    while (x) {
        x &= (x - 1); // Brian Kernighan's algorithm
        count++;
    }
    return count;
}

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

int main() {
    cout << "Bleak numbers up to 30: ";
    for (int i = 1; i <= 30; i++) {
        if (isBleakNumber(i))
            cout << i << " ";
    }
    cout << endl;
    
    // ทดสอบเฉพาะตัว
    cout << "3 is " << (isBleakNumber(3) ? "" : "not ") << "Bleak" << endl;
    cout << "4 is " << (isBleakNumber(4) ? "" : "not ") << "Bleak" << endl;
    
    return 0;
}

ผลลัพธ์

Bleak numbers up to 30: 1 2 4 8 16  (Note: 1 is bleak by definition as x>=1)
3 is not Bleak
4 is Bleak

Bleak Numbers แรกๆ

1, 2, 4, 8, 16, 32, 64, 128, ... (กำลังของ 2) และบางตัวอื่น เช่น 3? ไม่ 3 ไม่ใช่

จริงๆ แล้ว Bleak numbers คือ: 1, 2, 4, 8, 16, 32, ... และบางตัวที่ไม่ใช่กำลังของ 2 เช่น 91, 92, ...

การเพิ่มประสิทธิภาพ

แทนที่จะเช็คทุก x 1..n-1 สังเกตว่า countSetBits(x) ≤ log₂(x) + 1

ดังนั้น x ต้องอยู่ในช่วง [n - log₂(n) - 1, n-1] เท่านั้น

bool isBleakOptimized(int n) {
    int maxBits = 32 - __builtin_clz(n); // จำนวนบิตของ n
    int start = max(1, n - maxBits);
    for (int x = start; x < n; x++)
        if (x + __builtin_popcount(x) == n)
            return false;
    return true;
}

ลดจำนวน iteration จาก O(n) เป็น O(log n)