Tập hợp lớn nhất có OR bitwise = N C++

Cho số N. Tìm tập hợp lớn nhất các số trong [0, N] sao cho OR bitwise của tất cả = N.

Quan sát: x | N == N ⇔ mọi bit 1 của x cũng là bit 1 của N. Tức x là "submask" của N.

Tập hợp tất cả submask của N (kể cả 0) thỏa mãn và là lớn nhất.

Triển khai C++

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

void printSubmasks(int n) {
    for (int i = 0; i <= n; i++)
        if ((i | n) == n) cout << i << ' ';
    cout << endl;
}

int main() {
    printSubmasks(7); // 0 1 2 3 4 5 6 7
    return 0;
}

Kết quả

0 1 2 3 4 5 6 7

Số lượng: 2^(số bit 1 của N). Với N=7 (111₂) → 2³=8 phần tử.