Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
go ahead... be a heretic
 
PerlMonks  

How do I manipulate arrays of bits?

by faq_monk (Initiate)
on Oct 08, 1999 at 00:20 UTC ( #620=perlfaq nodetype: print w/ replies, xml ) Need Help??

Current Perl documentation can be found at perldoc.perl.org.

Here is our local, out-dated (pre-5.6) version:

Use pack() and unpack(), or else vec() and the bitwise operations.

For example, this sets $vec to have bit N set if $ints[N] was set:

    $vec = '';
    foreach(@ints) { vec($vec,$_,1) = 1 }

And here's how, given a vector in $vec, you can get those bits into your @ints array:

    sub bitvec_to_list {
        my $vec = shift;
        my @ints;
        # Find null-byte density then select best algorithm
        if ($vec =~ tr/\0// / length $vec > 0.95) {
            use integer;
            my $i;
            # This method is faster with mostly null-bytes
            while($vec =~ /[^\0]/g ) {
                $i = -9 + 8 * pos $vec;
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
                push @ints, $i if vec($vec, ++$i, 1);
            }
        } else {
            # This method is a fast general algorithm
            use integer;
            my $bits = unpack "b*", $vec;
            push @ints, 0 if $bits =~ s/^(\d)// && $1;
            push @ints, pos $bits while($bits =~ /1/g);
        }
        return \@ints;
    }

This method gets faster the more sparse the bit vector is. (Courtesy of Tim Bunce and Winfried Koenig.)

Log In?
Username:
Password:

What's my password?
Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (11)
As of 2014-04-16 14:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (427 votes), past polls