There are processor specific instructions for searching bit arrays. These may be provided as compiler intrinsic functions. Many Linux filesystems use these extensively.
__builtin_ffs() is one in GCC.
ffsll() may be POSIX although I haven't heard of it until now.
Can you say anything about the adjacent byte values that represent an empty pair?
I want to propose looking at the bytes rather than the bits.
Any given byte if it is to be the left hand contributer of a pair of empty 6 bits chars must fit a particular bit mask whose value depends upon his postion. ?? ?? 00 00 or ?? 00 00 00 or whatever. You can consider each byte in turn for their candidacy as a left most byte. A simple lookup table of which mask to use is possible.
Hence we don't actually have to pull out the 6bit chars before considering them.
Can we do better, having discarded a byte as a candidate, can we now skip the one to left?
In the case where our mask was 00 00 00 00 if that fails then the our neighbour to the left, yes if the first bit is set.
Does that actually make things any faster?
Process the 6-bit values in groups.
You could use groups of 5 values in a 32 bit word, which wastes 2 bits or about 7% space. If all values in a word are 0 then the word is zero, so it is fast to find a nonempty word, then inspect the 5 values in the word.
If you can't live with a little wasted space, use groups of 96 bits, where 96 is the least common multiple of 6 and 32. I.e. pack 16 values of 6 bits into three 32 bit words.
The best solution I found was:
1. make the items 1 byte (not 6 bits than before) - thanks Skizz
2. use a bitmap to see which item is the nearest on the left. This was much faster than going back with the technique described by djna.
The speed improvements are impressive:
in one test case, from 13s it's now 6.5s
in another one, from 7.4s to 3.6s
The performance has doubled :D
Thanks again for your answers!