UltraSet

#undef _GLIBCXX_DEBUG                                                   // bitset isn't working...
#define all(x) begin(x), end(x)
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

template<class A>
void addlog(A a) {
    cerr << a << endl;
}
template<class A, class... B>
void addlog(A a, B... b) {
    cerr << a << ' ';
    addlog(b...);
}

typedef uint64_t Long;
constexpr uint32_t W = 64;                                          // Long width.
constexpr uint32_t LOG_W = (uint32_t)log2(W);                       // Log2 of Long width.
constexpr uint32_t L = 1;                                           // # of longs.
constexpr uint32_t B = W * L;                                           // # of bits.
constexpr Long ONE = 1;

bool test_bit(Long mask, uint32_t bit) {
    return (mask >> bit) & ONE;
}

__attribute__((warn_unused_result))
Long set_bit(const Long mask, uint32_t bit) {
    return mask | (ONE << bit);
}

__attribute__((warn_unused_result))
Long reset_bit(const Long mask, uint32_t bit) {
    return mask & (~(ONE << bit));
}

void print_bits(ostream &out, const Long mask) {
    for (uint32_t i = 0; i < W; ++i) {
        out << test_bit(mask, i);
    } out << ' ';
}

struct ultra_set {
    bitset<L> not_empty;
    vector<Long> longs;
    bool zipped;

    vector<Long>::iterator iter;
    uint32_t iter_pos;

    void clear_iter() {
        iter = begin(longs);
        iter_pos = 0;
    }

    Long get_next_zipped() {
        if (not_empty[iter_pos]) {
            ++iter_pos;
            return *(iter++);
        } return 0;
    }

    // Zero-filling constructor.
    ultra_set(bool zip = true) {
        not_empty.reset();
        if (zip)
            longs.clear();
        else
            longs.assign(L, 0);
        zipped = zip;
    }

    void unzip() {
        assert(zipped == true);
        vector<Long> temp;
        temp.reserve(L);
        clear_iter();
        for (uint32_t i = 0; i < L; ++i)
            temp.push_back(get_next_zipped());
        swap(longs, temp);
        zipped = false;
    }

    void zip() {
        assert(zipped == false);
        vector<Long> temp;
        for (auto current : longs)
            if (current)
                temp.push_back(current);
        swap(longs, temp);
        zipped = true;
    }

    bool test(uint32_t k) const {
        assert(zipped == false);
        assert(k < B);
        uint32_t word = k >> LOG_W,  bit = k & (W - 1);
        return test_bit(longs[word], bit);
    }

    void set(uint32_t k) {
        assert(zipped == false);
        assert(k < B);
        uint32_t word = k >> LOG_W,  bit = k & (W - 1);
        longs[word] = set_bit(longs[word], bit);
        not_empty[word] = true;
    }

    void reset(uint32_t k) {
        assert(zipped == false);
        assert(k < B);
        uint32_t word = k >> LOG_W,  bit = k & (W - 1);
        longs[word] = reset_bit(longs[word], bit);
        if (longs[word] == 0)
            not_empty[word] = false;
    }

    // From left to right.
    friend ostream &operator<<(ostream &out, ultra_set &u) {
        if (u.zipped) {
            u.clear_iter();
            for (uint32_t i = 0; i < L; ++i) {
                print_bits(out, u.get_next_zipped());
            }
        } else {
            for (auto l : u.longs)
                print_bits(out, l);
        }
        return out;
    }
};


// |= first k bits.
void move_bits(ultra_set &from, ultra_set &to, uint32_t k) {
    assert(from.zipped && to.zipped);
    from.clear_iter();
    to.clear_iter();
    vector<Long> a_temp, b_temp;
    for (uint32_t i = 0; i < L; ++i) {
        Long a = to.get_next_zipped();
        Long b = from.get_next_zipped();
        if (k < W) {
            if (a | ((b << (W - k)) >> (W - k))) {
                a_temp.push_back(a | ((b << (W - k)) >> (W - k)));
                to.not_empty.set(i);
            } else {
                to.not_empty.reset(i);
            }

            if ((b >> k) << k) {
                b_temp.push_back((b >> k) << k);
                from.not_empty.set(i);
            } else {
                from.not_empty.reset(i);
            }

            break;
        } else {
            if (a | b) {
                a_temp.push_back(a | b);
                to.not_empty.set(i);
            }
            from.not_empty.reset(i);
            k -= W;
        }
    }
    swap(to.longs, a_temp);
    swap(from.longs, b_temp);
}

void get_bits(ultra_set &from, vector<uint32_t> &to) {
    assert(from.zipped == true);
    to.clear();
    from.clear_iter();
    for (uint32_t i = 0; i < L; ++i) {
        Long l = from.get_next_zipped();
        addlog("l =", l);
        if (l) {
            for (uint32_t j = 0; j < W; ++j, l >>= 1) {
                if (l & ONE) {
                    to.push_back(i + j); {
                    }
                }
            }
        }
    }
}

int main() {
    ultra_set a, b;
    a.unzip();
    b.unzip();
    a.set(1);
    a.set(3);
    a.set(5);
    b.set(2);
    b.set(4);
    a.zip();
    b.zip();
    addlog(a);
    addlog(b);
    move_bits(a, b, 5);
    addlog(a);
    addlog(b);
    vector<uint32_t> v;
    get_bits(b, v);
    for (auto e : v)
        cout << e << ' ';
    cout << endl;
    return 0;
}