Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: Locating a specified number of contiguous 0 bits within a large bitstring efficiently.

by Grimy (Pilgrim)
on Jun 06, 2013 at 17:05 UTC ( [id://1037490]=note: print w/replies, xml ) Need Help??


in reply to Locating a specified number of contiguous 0 bits within a large bitstring efficiently.

use strict; use warnings; # $leading_0s[$n] is a regex matching any byte that begins with at lea +st $n '0' bits my @leading_0s = (qr//, map { my $max = chr(0xFF >> $_); qr/[\0-$max]/; } 1..8); # $trailing_0s[$n] is a regex matching any byte that ends with at leas +t $n '0' bits my @trailing_0s = (qr//, map { my $step = 1 << $_; my @ok = map { chr($step * $_) } 0..0xFF >> $_; local $" = q[]; qr/[\Q@ok\E]/ } 1..8); # Test if a string contains $n consecutive '0' bits. # If yes, returns the bit offset of the match. # Otherwise, returns -1. sub match_0s { my $n = shift; # number of consecutive '0' bits to be matched local $_ = shift || $_; # string to match against for my $trailing (0..8) { my $full = $n - $trailing >> 3; my $leading = $n - $trailing & 7; if (/$trailing_0s[$trailing]\0{$full}$leading_0s[$leading]/) { return $-[0] << 3 | -$trailing & 7; } } return -1; } $_ = "ABC`\0abc"; print match_0s(14), $/; # 27 print match_0s(15), $/; # -1 print match_0s(24, 0.0.0), $/; # 0

Tested, but not benchmarked. It may or may not be faster that the straightforward approach using unpack. To change endianness, just switch @leading_0s and @trailing_0s.

EDIT: now works even when the string is made entirely of null bytes.

EDIT: doesn't work for $n < 8. This case is left as an exercise to the reader. (:

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

    This works perfectly, and fairly quickly. Thankyou.


    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.
      I don't see how this can work for $N<8; in fact, it doesn't:
      match_0s(1,"\201\201\201\201") => -1

        Oops, thanks for catching that.

        I edited my previous post.

        Indeed. My benchmark code was using a random generator that was not producing values < 8. Now fixed. Thanks.


        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1037490]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (4)
As of 2024-03-29 13:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found