Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

comparing bit vectors

by citromatik (Curate)
on Jun 11, 2009 at 09:48 UTC ( [id://770578]=perlquestion: print w/replies, xml ) 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'?

Thanks in advance

citromatik

Replies are listed 'Best First'.
Re: comparing bit vectors
by BrowserUk (Patriarch) 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");

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others sharing their wisdom with the Monastery: (4)
As of 2024-03-29 05:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found