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 ( #1037490=note: print w/replies, xml ) Need Help??

```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;
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. (:

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

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.

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? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (3)
As of 2023-10-04 22:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?