Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

comparing bit vectors

by citromatik (Curate)
on Jun 11, 2009 at 09:48 UTC ( #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

Comment on comparing bit vectors
Select or Download Code
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");

Log In?
Username:
Password:

What's my password?
Create A New User
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? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (9)
As of 2014-12-22 11:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (116 votes), past polls