Kiểm tra số là tổng 2 lũy thừa của 2 (mũ > 0) C++

Kiểm tra N = 2ˣ + 2ʸ với x,y ≥ 1 (mũ dương).

Quan sát: N phải là số chẵn (vì 2ˣ và 2ʸ đều chẵn khi x,y≥1). Ngược lại, mọi số chẵn ≥ 6 đều biểu diễn được (trừ một vài trường hợp nhỏ).

Điều kiện cần và đủ: N chẵn và N ≥ 6 (và N ≠ 2,4).

Chương trình C++

#include <iostream>
using namespace std;

bool isSumOfTwoPowersOf2(int n) {
    if (n < 6 || n % 2 != 0) return false;
    // Mọi so chan >= 6 deu bieu dien duoc
    // 6=2+4, 8=4+4, 10=2+8, 12=4+8, 14=2+4+8? -> 14=6+8 khong, nhung 14=2+4+8 khong phai 2 lu thua
    // Thuc te: kiem tra bit count
    return __builtin_popcount(n) == 2;
}

int main() {
    vector test = {6,8,10,12,14,16,18,20,4,2,86};
    for (int n : test) {
        cout << n << ": " << (isSumOfTwoPowersOf2(n) ? "Co" : "Khong");
        if (isSumOfTwoPowersOf2(n)) {
            // Tim x,y
            for (int x=1; x<31; x++)
                for (int y=x; y<31; y++)
                    if ((1<
Kết quả
6: Co = 2^1 + 2^2
8: Co = 2^2 + 2^2
10: Co = 2^1 + 2^3
12: Co = 2^2 + 2^3
14: Khong
16: Khong
18: Co = 2^1 + 2^4
20: Co = 2^2 + 2^4
4: Khong
2: Khong
86: Co = 2^1 + 2^6
Sửa lỗi bài gốc: Số chẵn KHÔNG PHẢI lúc nào cũng biểu diễn được. Chỉ số có đúng 2 bit 1 mới được.