In tập con bitwise AND của số N trong C++

In tất cả số i từ 0 đến n sao cho i & n = i (tức i là tập con bit của n). Ví dụ n=6 (110) → 0,2,4,6. Công thức: i = (i-1) & n lặp từ n về 0.

Thuật toán bit

Khởi tạo i=n. Lặp: in i, cập nhật i = (i-1) & n. Dừng khi i=0 (in 0 cuối cùng). Độ phức tạp O(2^k) với k số bit 1 của n.

Ví dụ minh họa

#include <iostream>
using namespace std;

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

Kết quả

11 10 9 8 3 2 1 0