Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Efficient bit counting with a twist.

by AnomalousMonk (Monsignor)
on Jan 27, 2013 at 09:48 UTC ( #1015571=note: print w/ replies, xml ) Need Help??


in reply to Efficient bit counting with a twist.

Maybe I just don't understand the question, but assuming  unpack '%32b*', ...   is sufficiently efficient, wouldn't a count on the  'b' template specifier serve to count the set bits from the beginning of the string up to but not including a given bit offset?

>perl -wMstrict -le "my $b = qq{\x01\x03\x07\xff\xfe\xfc}; ;; print ' 1111111111222222222233333333334444444444'; print '0123456789' x 5; print unpack 'b*', $b; print '' ;; for my $offset (0, 1, 7 .. 10, 15 .. 20, 24 .. 28, 30 .. 32) { my $c = unpack qq{%32b$offset}, $b; my $vc = vec_sum($b, $offset); die qq{pack sum $c != vec sum $vc} if $c != $vc; printf qq{before bit at offset %2d: %2d bits set \n}, $offset, $c; } ;; sub vec_sum { my ($v, $p) = @_; ;; my $c = 0; vec($v, $_, 1) and ++$c for 0 .. $p - 1; return $c; } " 1111111111222222222233333333334444444444 01234567890123456789012345678901234567890123456789 100000001100000011100000111111110111111100111111 before bit at offset 0: 0 bits set before bit at offset 1: 1 bits set before bit at offset 7: 1 bits set before bit at offset 8: 1 bits set before bit at offset 9: 2 bits set before bit at offset 10: 3 bits set before bit at offset 15: 3 bits set before bit at offset 16: 3 bits set before bit at offset 17: 4 bits set before bit at offset 18: 5 bits set before bit at offset 19: 6 bits set before bit at offset 20: 6 bits set before bit at offset 24: 6 bits set before bit at offset 25: 7 bits set before bit at offset 26: 8 bits set before bit at offset 27: 9 bits set before bit at offset 28: 10 bits set before bit at offset 30: 12 bits set before bit at offset 31: 13 bits set before bit at offset 32: 14 bits set

Update: Example code changed to include check against  vec sum algorithm given in OP; also made things a bit prettier.


Comment on Re: Efficient bit counting with a twist.
Select or Download Code
Re^2: Efficient bit counting with a twist.
by BrowserUk (Pope) on Jan 27, 2013 at 10:44 UTC

    Whatever makes you think it could possibly be that obviously simple? (<<< a link!)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1015571]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (7)
As of 2014-08-23 06:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (172 votes), past polls