### comparing bit vectors

by citromatik (Curate)
 on Jun 11, 2009 at 09:48 UTC Need Help??
citromatik has asked for the wisdom of the Perl Monks concerning the following question:

Hi all

In a recent post, someone asked how to find if two numeric ranges overlap. I couldn't resist to try a solution based on bit vectors. That is, create 2 bit vectors with the bits inside the range set to "1", and see if the & operation on them give something different to a vector of '0's. Something like:

```use strict;
use warnings;

my (\$bv1,\$bv2,\$bv3) = ('') x 3;
vec (\$bv1,\$_,1)=1 for (11..19)  # First range
vec (\$bv2,\$_,1)=1 for (15..25)  # Second range
vec (\$bv3,19,1)=0                      # The "0" vector -- should have
+ the length of the shorter.

print unpack ("b*",\$bv1),"\n";
print unpack ("b*",\$bv2),"\n";
print unpack ("b*",\$bv3),"\n",'-'x60,"\n";
my \$olap = \$bv1 & \$bv2;
print unpack ("b*",\$olap),"\n\n";

print +((\$bv1 & \$bv2) eq \$bv3 ? "don't overlap\n" : "overlap\n");

This works as expected:

```1  000000000001111111110000
2  00000000000000011111111111000000
0s 000000000000000000000000
------------------------------------------------------------
&  000000000000000111110000

but I find a bit tricky to have to build the '0' vector for comparisons and the fact that the bit vectors 000 and 0000000000000000 are not equals

Is there a better way to see if a bit vector has all its bits set to '0'?

citromatik

Replies are listed 'Best First'.
Re: comparing bit vectors
by BrowserUk (Pope) on Jun 11, 2009 at 10:15 UTC
Is there a better way to see if a bit vector has all its bits set to '0'?

Yes. Combine the checksumming (%nn) and bit (b*) formats of unpack:

```## 800 zero bits
\$bitVec = chr(0) x 100;;
print unpack '%32b*', \$bitVec;;
0

## Set 1 bit in the middle
substr \$bitVec, 50, 1, chr(1);;
print unpack '%32b*', \$bitVec;;
1

## set 8 bits in the middle
[0] Perl> substr \$bitVec, 50, 1, chr(255);;
[0] Perl> print unpack '%32b*', \$bitVec;;
8

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.
Re: comparing bit vectors
by almut (Canon) on Jun 11, 2009 at 10:52 UTC

You could also match against non-zero bytes/characters, i.e. [^\0]. In case of overlap there will be one or more non-zero bytes.

```print +((\$bv1 & \$bv2) =~ /[^\0]/ ? "overlap\n" : "don't overlap\n");

Create A New User
Node Status?
node history
Node Type: perlquestion [id://770578]
Approved by marto
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (9)
As of 2017-06-26 14:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (580 votes). Check out past polls.