พิมพ์ชุดย่อย Bitwise AND ของจำนวน N ใน C++

โจทย์

ให้จำนวน N ต้องการพิมพ์ตัวเลขจาก 0 ถึง N ที่เป็นผลลัพธ์ของ Bitwise AND กับ N (คือ i & N = i)

ตัวอย่าง: N=4 → 0, 4 (เพราะ 0&4=0, 1&4=0, 2&4=0, 3&4=0, 4&4=4)

N=6 → 0, 2, 4, 6

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

ใช้คุณสมบัติ: ชุดย่อยของ N ในระดับบิต คือตัวเลข i ที่ i & N == i

สามารถสร้างได้โดยลูปย้อนกลับ: i = (i-1) & N เริ่มจาก i = N ลงมา 0

อัลกอริทึม

Step 1: Loop จาก n ถึง 1 โดย i = (i-1) & n
Step 2: พิมพ์ i
Step 3: พิมพ์ 0 ท้ายสุด
Step 4: จบ

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

#include <iostream>
using namespace std;

int main() {
    int n = 11;
    for (int i = n; i > 0; i = (i - 1) & n)
        cout << i << " ";
    cout << 0;
    return 0;
}

ผลลัพธ์

11 10 9 8 3 2 1 0