in reply to Re^4: 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.

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.
  • Comment on Re^5: Locating a specified number of contiguous 0 bits within a large bitstring efficiently.
  • Select or Download Code

Replies are listed 'Best First'.
Re^6: Locating a specified number of contiguous 0 bits within a large bitstring efficiently.
by BrowserUk (Patriarch) on Jun 07, 2013 at 20:23 UTC

    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]
        First of all, my code doesn't do $N < 8 ... so you'd only expect to see correct answers from 5 on down.

        Obvious. (Once someone kindly points it out.)

        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

        Indeed, mine! (A dumb typo.) 

        C:\test>b-zeroBits.pl -N=1e5
Name "main::N" used only once: possible typo at C:\test\b-zeroBits.pl 
+line 1.
0100100010000100000100000010000000100000000100000000010000000000100000
+00000010000000
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 : 104
wrog: 15 : 119
wrog: 16 : 135
wrog: 17 : 152

        [download]

        My only excuse is attempting to give timely response to your efforts, whilst also construct a descent testbed and benchmark for 4 different approaches (3 posted + my own.). My own attempt -- essentially based on the ideas in the OP -- is proving to be a pain to code.

        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]

In Section Seekers of Perl Wisdom