การแทนจำนวนเต็มเป็นผลรวมของกำลังสอง (Powers of 2) ใน C++

ในปัญหานี้ ให้จำนวนเต็ม N ต้องหาเลขยกกำลังที่เมื่อนำ 2 ยกกำลังแล้วรวมกันได้ N

ตัวอย่าง

Input − 17

Output − 0, 4

คำอธิบาย − 17 = 2⁴ + 2⁰ = 16 + 1

หลักการ

ทุกจำนวนเต็มสามารถแทนเป็นผลรวมของกำลังสองได้ ซึ่งก็คือการแปลงเป็นเลขฐานสอง (Binary)

ตัวอย่าง: 17 ในฐานสอง = 10001₂ → บิตที่ 1 อยู่ตำแหน่ง 0 และ 4

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

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

void sumPower(long int x) {
    vector<long int> powers;
    while (x > 0) {
        powers.push_back(x % 2); // เก็บบิต (0 หรือ 1)
        x = x / 2;
    }
    for (int i = 0; i < powers.size(); i++) {
        if (powers[i] == 1) {
            cout << i;
            if (i != powers.size() - 1) cout << ", ";
        }
    }
    cout << endl;
}

int main() {
    int number = 23342;
    cout << "Powers of 2 that sum upto " << number << " are : ";
    sumPower(number);
    return 0;
}

ผลลัพธ์

Powers of 2 that sum upto 23342 are : 1, 2, 3, 5, 8, 9, 11, 12, 14

การตรวจสอบ

2¹ + 2² + 2³ + 2⁵ + 2⁸ + 2⁹ + 2¹¹ + 2¹² + 2¹⁴
= 2 + 4 + 8 + 32 + 256 + 512 + 2048 + 4096 + 16384
= 23342 ✓