Efficient way of creating a bit matrix and scan set columns

Question

This is my current problem, I have a number of Bloom filters which I wanted to construct into a matrix, say:

[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
...
[1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0]

Each column will be derived from a BitSet, is there a more efficient way to find all columns that have a bits set to 1, apart from looping all rows and comparing each index?

Is there any data structure that could help me with this?

Answer 1

Assuming you're looking for which columns contain ones and now how many ones each column contains, looping through them seems like the best idea.

If you implement your loops with some short-circuit logic, then you'll get a better average running time.

Something like:

for (int column = 0; column < width; column++) {
    for (int row = 0; row < height; row++) {
        if (array[column][row] == 1) {
            list.append(column);
            break;  // move on to the next column because we don't care what's 
                    // left in this column as we already found our '1'

With this code, you'll get a worst-case (if every bit is 0) running time of n (n being the total number of bits) which is pretty good.

But unless you're extremely unlucky, you'll get a much better running time due to the short-circuit logic.

The above works for arrays of bits, however, BitSets have some useful functionality of their own.

A BitSet contains the functions: length() which returns the highest index with a set bit + 1 (or 0 if there are no set bits) and nextSetBit(index) which returns the index of the next set bit from index -> end inclusive.

So you're code could easily be something like:

int index = 0;

while (index < BitSet.length()) {
    index = BitSet.nextSetBit(index);
    list.append(index);
    index++;
}