Quick thought, as I won't have time to dedicate to code-example before tonight, but in case it sparks a line of thought for you -- This is specifically to address the "I don't want it to keep rotating the bits over and over again" problem.

Might a combination of rotation and mask help?

Have an initializer which sets up all possible aligned bitmask searches, and then a routine which loops through all the pre-built masks looking for a match?

In this short example which will likely be fraught with errors, assuming we are looking for 0b1010 in 0b00110100101. For readability's sake, this example plays on an 8-bit alignment requirement; simply increase the work of the initializer and searcher routines to take advantage of 64-bit alignment capabilities.

The initializer sets up the following array of pre-rotated bitmasks:

mask[0] = 0b11110000; mask[1] = 0b01111000; mask[2] = 0b00111100; mask[3] = 0b00011110; mask[4] = 0b00001111;

I'm running on light air here, I think you'll need to also set up an array of pre-rotated comparison bitstrings:

seabits[0] = 0b10100000; seabits[1] = 0b01010000; seabits[2] = 0b00101000; seabits[3] = 0b00010100; seabits[4] = 0b00001010;

Then the main comparison routine iterates across the main bit buffer using these pre-built masks and values to ascertain if there is a match.

Multilingual psuedocode for the main comparison routine:

for (chunkcol = 0; chunkcol < (BitBufferLength / CHUNKSIZE); chunk +col++) { foreach $masknum (@mask) { if ( ( BitBuffer[chunkcol] & mask[$masknum] ) == $seabit +s[$masknum]) { return ( ( chunkcol * CHUNKSIZE) + $masknum ); +# FIXME: Check for fenceposting error(s) } } } return ($RET_NOTFOUND);

I should think a static accumulator can track which bit column you find the match in and simply exit the loop returning that value?

I started coding a proof-of-concept in Perl but as soon as I got into the guts of it I knew this was going to take me longer than I have left this morning.

Hope this got my point across and hope it either yields some inspiration or you already thought of it and have moved on. :-)


Update: Fixed bitmask and searchbits arrays.
Update: Added psuedocode.
Update: Updated chunking in psuedocode.


In reply to Re: [OT] The interesting problem of comparing bit-strings. by marinersk
in thread [OT] The interesting problem of comparing bit-strings. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":