จำนวนเฉพาะของบิตเซต (Set Bits) ในการแทนค่าบाइनารีใน C++

ภาพรวมปัญหา

ได้รับจำนวนเต็ม L และ R ต้องนับจำนวนตัวเลขในช่วง [L, R] ที่มีจำนวนบิต 1 (set bits) ในรูปแบบไบนารีเป็นจำนวนเฉพาะ

ตัวอย่าง

Input: L = 7, R = 12
Output: 6
Explanation:
7  → 111  (set bits = 3, เฉพาะ)
8  → 1000 (set bits = 1, ไม่เฉพาะ)
9  → 1001 (set bits = 2, เฉพาะ)
10 → 1010 (set bits = 2, เฉพาะ)
11 → 1011 (set bits = 3, เฉพาะ)
12 → 1100 (set bits = 2, เฉพาะ)

วิธีแก้ปัญหา

1. วนลูปทุกตัวเลขในช่วง [L, R]
2. นับ set bits ด้วยฟังก์ชัน built-in ของ C++: __builtin_popcount()
3. ตรวจสอบว่าจำนวน set bits เป็นจำนวนเฉพาะหรือไม่
4. นับจำนวนที่ผ่านเกณฑ์

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

void printPrimeSetBits(int l, int r) {
    int tot_bit, count = 0;
    for (int i = l; i <= r; i++) {
        tot_bit = __builtin_popcount(i);
        if (isPrimeNumber(tot_bit))
            count++;
    }
    cout << count;
}

int main() {
    int L = 7, R = 13;
    cout << "Total numbers with prime set bits between " << L << " and " << R << " are : ";
    printPrimeSetBits(L, R);
    return 0;
}

ผลลัพธ์

Total numbers with prime set bits between 7 and 13 are : 6