Bitlar toʻplami

Introduction

Suppose we have a set of elements $S$ , and every element is bounded by $X$ . In other words, for every $x \in S$ , we have

0 \leq x < X

There are many ways to store such a set, for example:

std::array
std::vector
std::set

Each of them has its own advantages. For example, some allow fast insertion and deletion, while others support operations like lower_bound in .

Bitlar toʻplami - Resources

O(\log N)

O (lo g N)

But what if we want to perform operations such as:

union of two sets;
intersection;
subtraction.

Can we make these operations faster?

Using an Array

Let us start with a simple array-based implementation.

The operations we want are:

insert an element into the set;
erase an element from the set;
check whether an element belongs to the set;
find the union of two sets.

The first three operations are easy to implement in $O(1)$ time:

However, union is slower. To compute the union of two sets, we have to scan all positions, which takes $O(X)$ time.

Improving the Array Representation

Notice that the array stores only 0 or 1.

So instead of storing one integer per element, we can pack many values into the bits of an integer.

For example, we can split the array into blocks of size $64$ .

Each block can be stored as unsigned long long.

Suppose the $i$ -th block is b[i]. Then the $j$ -th bit of block $i$ is equal to 1 if and only if the element

i \cdot 64 + j

belongs to the set.

This gives the following implementation:

Now the union operation works on blocks instead of individual elements, so it takes only

O\left(\frac{X}{64}\right)

time.

So compared to the array version, we gain a factor of about $64$ in practice.

Built-in Bitset

Instead of writing our own structure, we can often use the standard C++ container:

It provides the same main idea and supports many useful bit operations directly.

Exercises

Given the structure Set implemented with bit blocks, write a function GetMin() that returns the minimum element of the set. Do the same for GetMax(). The required complexity is $O\left(\frac{X}{64}\right)$ .
Given the same structure, implement GetNext(x), which returns the smallest element greater than x. The required complexity is $O\left(\frac{X}{64}\right)$ .

struct Set {
    int a[X];

    Set() {
        for (int i = 0; i < X; i++) {
            a[i] = 0;
        }
    }

    void Insert(int x) {
        a[x] = 1;
    }

    void Erase(int x) {
        a[x] = 0;
    }

    bool Check(int x) {
        return a[x];
    }
};

struct Set {
    ...

    void Union(Set T) {
        for (int i = 0; i < X; i++) {
            if (T.Check(i)) {
                Insert(i);
            }
        }
    }
};

struct Set {
    int X;
    vector<unsigned long long> b;

    Set(int X_) : X(X_), b(X / 64 + 1, 0) {}

    void Insert(int x) {
        b[x / 64] |= (1ULL << (x % 64));
    }

    void Erase(int x) {
        if (Check(x)) {
            b[x / 64] ^= (1ULL << (x % 64));
        }
    }

    bool Check(int x) {
        return (b[x / 64] & (1ULL << (x % 64))) != 0;
    }

    void Union(const Set& T) {
        for (int i = 0; i <= X / 64; i++) {
            b[i] |= T.b[i];
        }
    }
};

std::bitset