Bitset Optimization

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Adjust MAXN to the maximum n you expect at compile time for std::bitset
5
static const int MAXN = 2048;
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    // Example graph with n nodes
12
    int n = 6;
13
    vector<bitset<MAXN>> reach(n);
14
15
    // Sample directed edges
16
    vector<pair<int,int>> edges = {
17
        {0,1},{1,2},{2,3},{3,4},{1,4},{4,5}
18
    };
19
20
    // Initialize reachability: self loops and edges
21
    for (int i = 0; i < n; ++i) reach[i].set(i);
22
    for (auto [u,v] : edges) reach[u].set(v);
23
24
    // Bitset-accelerated transitive closure
25
    // For each intermediate k, propagate its reachability row to any i that can reach k
26
    for (int k = 0; k < n; ++k) {
27
        for (int i = 0; i < n; ++i) {
28
            if (reach[i].test(k)) { // O(1) test
29
                reach[i] |= reach[k]; // O(n/64) word-wise OR
30
            }
31
        }
32
    }
33
34
    // Print reachability matrix
35
    cout << "Reachability matrix (1 if i reaches j):\n";
36
    for (int i = 0; i < n; ++i) {
37
        for (int j = 0; j < n; ++j) cout << (reach[i].test(j) ? '1' : '0');
38
        cout << '\n';
39
    }
40
41
    // Example query: can 0 reach 5?
42
    cout << "0 reaches 5? " << (reach[0].test(5) ? "Yes" : "No") << '\n';
43
    return 0;
44
}
45

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Max capacity; adjust as needed
5
static const int MAXW = 100000; // supports capacity up to 100000
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    // Example: given item weights, check achievable sums up to W
12
    int n = 6;
13
    int W = 50;
14
    vector<int> w = {3, 7, 12, 19, 5, 9};
15
16
    bitset<MAXW + 1> dp; // dp[s] == 1 iff sum s is achievable
17
    dp.set(0);           // sum 0 is always achievable
18
19
    for (int x : w) {
20
        // Shift achievable sums by x and OR to add new achievable sums
21
        dp |= (dp << x); // O(W/64) per item
22
    }
23
24
    // Mask out bits beyond capacity W to be safe (optional if MAXW == W)
25
    for (int s = W + 1; s <= MAXW; ++s) dp.reset(s);
26
27
    // Output: maximum achievable sum <= W and whether exact W is achievable
28
    int best = -1;
29
    for (int s = W; s >= 0; --s) if (dp.test(s)) { best = s; break; }
30
31
    cout << "Exact W achievable? " << (dp.test(W) ? "Yes" : "No") << '\n';
32
    cout << "Max achievable <= W: " << best << '\n';
33
34
    return 0;
35
}
36

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct DynBitset {
5
    int nbits;                 // logical number of bits
6
    vector<unsigned long long> w; // words storing the bits
7
8
    explicit DynBitset(int n = 0) { reset_size(n); }
9
10
    void reset_size(int n) {
11
        nbits = n;
12
        int L = (n + 63) / 64;
13
        w.assign(L, 0ULL);
14
    }
15
16
    void set(int i) {
17
        int j = i >> 6; int r = i & 63;
18
        w[j] |= (1ULL << r);
19
    }
20
    void reset(int i) {
21
        int j = i >> 6; int r = i & 63;
22
        w[j] &= ~(1ULL << r);
23
    }
24
    bool test(int i) const {
25
        int j = i >> 6; int r = i & 63;
26
        return (w[j] >> r) & 1ULL;
27
    }
28
29
    // In-place OR
30
    void ior(const DynBitset& other) {
31
        int L = (int)w.size();
32
        for (int j = 0; j < L; ++j) w[j] |= other.w[j];
33
    }
34
    // In-place AND
35
    void iand(const DynBitset& other) {
36
        int L = (int)w.size();
37
        for (int j = 0; j < L; ++j) w[j] &= other.w[j];
38
    }
39
40
    // Count set bits using hardware popcount
41
    long long count() const {
42
        long long c = 0;
43
        for (auto x : w) c += __builtin_popcountll(x);
44
        return c;
45
    }
46
47
    // Compute |A ∩ B| without allocating a new bitset
48
    static long long intersection_count(const DynBitset& A, const DynBitset& B) {
49
        int L = (int)A.w.size();
50
        long long c = 0;
51
        for (int j = 0; j < L; ++j) c += __builtin_popcountll(A.w[j] & B.w[j]);
52
        return c;
53
    }
54
};
55
56
int main() {
57
    ios::sync_with_stdio(false);
58
    cin.tie(nullptr);
59
60
    int M = 1000; // universe size
61
    DynBitset A(M), B(M);
62
63
    // Build two sets
64
    vector<int> elemsA = {1,3,5,7,10,42,128,256,512,700,900};
65
    vector<int> elemsB = {3,7,11,42,129,256,513,700,901};
66
    for (int x : elemsA) A.set(x);
67
    for (int x : elemsB) B.set(x);
68
69
    long long inter = DynBitset::intersection_count(A, B);
70
71
    cout << "|A ∩ B| = " << inter << "\n";
72
73
    // Example: union count = |A| + |B| - |A ∩ B|
74
    long long union_count = A.count() + B.count() - inter;
75
    cout << "|A ∪ B| = " << union_count << "\n";
76
77
    return 0;
78
}
79