Boolean function for the rescue

Author:	Wojciech Muła
Added on:	2015-10-25

The problem is defined as follows: a set of features is saved using bit-sets (usually large), and there is a list/map/whatever of sets containing features of different objects. We have to find which features are unique.

Naive solution is to use nested loops:

bit_set find_unique(list) {
    unsigned size = FEATURES_COUNT;
    bit_set  result(size);

    for (auto i=0; i < size; i++) {

        unsigned count = 0;
        for (auto& set: list) {
            if (set.is_set(i)) {
                count += 1;
            }
        }

        if (count == 1) {
            result.set(i);
        }
    }

    return result;
}

Not good, the method is_set of bit-set is called size * list.size() times. Even if a compiler is able to inline the call and use simple bit tests instructions it's still too expansive. Bit-set implementations always use arrays of integers to store the data, thanks to that bit-operations (and, or, xor, etc.) are executed very fast. We try to exploit this with boolean functions.

Each feature could be described as:

• non-existing (count is 0),
• unique (count is 1),
• non-unique (count greater than 1).

Now these states are encoded using two bits:

H	L	value
0	0	non-existing
0	1	unique
1	1	non-unique

Then we define a transition table. For example if a feature is present and the current value is 'unique' then the next value is 'non-unique' (row 5th).

H	L	feature	H'	L'
0	0	0	0	0
0	1	0	0	1
1	1	0	1	1
0	0	1	0	1
0	1	1	1	1
1	1	1	1	1

Boolean expressions are: L' = L or feature; H' = H or (feature and L).

We also need to get single bit-set from H and L at the end:

H	L	result
0	0	0
0	1	1
1	1	0

The final boolean expression is: result = L and not H.

Now we can rewrite the code:

class unique_checker {

    unsigned  size;
    bit_set   L, H;

public:
    unique_checker(unsigned size)
        : size(size)
        , L(size)
        , H(size) {}

    void update(const bit_set& set) {

        assert(set.size() == size);

        H = H | (set & L);  // we suppose that bit_set overloads bit-operator
        L = L | set;
    }

    bit_set finalize() const {

        return L | ~H;
    }
};

bit_set find_unique2(list) {

    unique_checker checker(FEATURES_COUNT);

    for (auto& set: list) {
        checker.update(set);
    }

    return checker.finalize();
}

I really like this approach.