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;

[download]

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;

[download]

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);

[download]

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":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.