in reply to Re^3: Locating a specified number of contiguous 0 bits within a large bitstring efficiently.
in thread Locating a specified number of contiguous 0 bits within a large bitstring efficiently.

Thank you for all the work you've put into this.

But whilst this finds a match (if it exists), I'm having the same problem with this as I am with my attempts to implement Dave_the_M's suggestion, that of converting the match to a bit position at which it was found?

$-[0] tells me the byte position, but then I need to work the byte at than position back to the pattern than matched and then the bit offset within it. Thoughts?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
  • Comment on Re^4: Locating a specified number of contiguous 0 bits within a large bitstring efficiently.

Replies are listed 'Best First'.
Re^5: Locating a specified number of contiguous 0 bits within a large bitstring efficiently.
by wrog (Friar) on Jun 07, 2013 at 05:36 UTC
    Put in match groups, i.e., replace 
    my $p = join '|', map { "$pre[$_]\\0{@{[($N-$_)>>3]}}$suf[($N-$_)&0x7]
+" } 0..7;

    [download]
    with 
    my $p = join '|', map { "$pre[$_](\\0{@{[($N-$_)>>3]}}$suf[($N-$_)&0x7
+])" } 0..7;

    [download]
    By construction, only one will match and $#- will tell you which one. We place the leftparen so that the group always starts at the first byte that's beginning with a zero bit. Then you just have to subtract the number of zero bits at the end of the byte that $pre[$_] is matching, but that's just $#- - 1. So the answer is 
    $-[$#-]*8 - $#- + 1

    [download]
    Still needs a bit more work to handle the $N < 8 case.
[reply]
[d/l]
[select]

      Unfortunately, the bitpatterns you generate -- in common with those used by grimey's code -- are not compatible with vec.

      By way of example, this generates a vector with a single length 1x0 run, and a single length 2x0 run; and single length 3x0 run; and so on: 

      $vec = ''; 
$n=-1; 
vec( $vec, $n+=$_, 1 ) = 1 for 2 .. 17; 
print unpack 'b*', $vec;;
0100100010000100000100000010000000100000000100000000010000000000100000
+000000100000000000010000000000000100000000000000100000000000000010000
+0000000000001000...
# 2  5   9    14    20     27      35       44        54         65   
+       77           90            104            119             135 
+             152

      [download]

      Thus, a search for

      • 1 x 0 should be found at position 0;
      • 2 x 0 should be found at position 2;
      • 3@5; 4@9; 5@14; ...

      Running your code looking for these runs against that vector produces:

      wrog  1: 0
wrog  2: 14
wrog  3: 5
wrog  4: 14
wrog  5: 14
wrog  6: 20
wrog  7: 27
wrog  8: 35
wrog  9: 44
wrog  10: 54
wrog  11: 65
wrog  12: 77
wrog  13: 90
wrog  14: 90
wrog  15: 90
wrog  16: 90
wrog  17: 90

      [download]

      I believe this is because little-endian bytes are bytes swapped and word swapped relative to big-endian.

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
[select]
        First of all, my code doesn't do $N < 8

        More explicitly, neither my nor grimey's versions handles the cases where the run of zeroes occurs entirely inside one byte,

        which in this example happens for $N in 1..4,

        so you'd only expect to see correct answers from 5 on down.

        Secondly, I'm getting the correct numbers for 14..17 when I run it so I'm guessing there's something else going on with either your testbed or mine

[reply]

In Section Seekers of Perl Wisdom