Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Power of two round up.

by boo_radley (Parson)
on Dec 15, 2000 at 22:59 UTC ( #46889=CUFP: print w/ replies, xml ) Need Help??

This is for a question that Dominus posed in the chatterbox. binround will return the next highest power of two. the code is a little test script for it. based off the dec2bin recipie from the cookbook.
for ($foo=1; $foo<211;$foo++){ print "$foo ". dec2bin($foo) . " binrounded is "; $binfoo= (binround ($foo)); print "$binfoo\n"; } sub binround{ my $str = unpack("B32", pack("N", shift)); $str =~ s/^0+(?=\d)//; $str=~/^.(.*)/; #first char should always be 1, thanks to above. $str="1" . "0" x (length ($1)+(($1=~/1/))); } sub dec2bin { my $str = unpack("B32", pack("N", shift)); $str =~ s/^0+(?=\d)//; # otherwise you'll get leading zeros return $str; }

Comment on Power of two round up.
Download Code
Re (tilly) 1: Power of two round up.
by tilly (Archbishop) on Dec 15, 2000 at 23:15 UTC
    TIMTOWTDI
    sub binround { my $out = 1; my $in = shift; while ($in) { $in >>= 1; $out += $out; } $out; }
      And an even faster WTDI:
      sub next_pwr { my ($x,$p) = (@_,2); # default to next_pwr(X,2) my $log = log($x)/log($p); $log = int($log+1) if $log != int($log); return $p**$log; }
      You can even add a log() memoization in there:
      { my %LOG = (2 => log(2)); # most common sub next_pwr { my ($x,$p) = (@_,2); # default to next_pwr(X,2) # assertions, etc. die "illegal base: $p" if $p < 2; return 1 if $x == 1; $p = int $p; my $log = ($LOG{$x} ||= log($x)) / ($LOG{$p} ||= log($p)); $log = int($log+1) if $log != int($log); return $p ** $log; } }


      japhy -- Perl and Regex Hacker
Re: Power of two round up.
by runrig (Abbot) on Dec 15, 2000 at 23:41 UTC
    my $num = 17; my $nlog = 2**(int(log($num)/log(2))+1); print $nlog;
Re: Power of two round up.
by I0 (Priest) on Dec 15, 2000 at 23:41 UTC
    local $_ = (shift)-1; $_ |= $_>>1; $_ |= $_>>2; $_ |= $_>>4; $_ |= $_>>8; $_ |= $_>>16; return ++$_
      I'm amazed at how clever this is, and I'm going to use it in my program. Thanks a lot.

        Although it's a technique more appropriate in a C program. In Perl, log($_)/log(2) benchmarks faster. (assuming it rounds properly at the boundaries)
        Update: My earlier timethese qq{} may have been misleading. With timethese sub{} the | >> method comes out faster
      Just to give Dominus more heebie jeebies :)
      sub round_up { local $_ = (shift)-1; my $num = (2**int(log($_)/log(2)))-1; return ++($_ |= $num); }
      On the other hand,

      If you want to use horrible and/or (somewhat) obfuscated code, you could try:

      sub shifty { my $v = (shift)-1; map { return ++$v } map { $v |= $v >> $_ } (1,2,4,8,16); }
      or alternately (the readable version):
      sub shifty2 { my $v = (shift)-1; $v |= $v >> $_ foreach (1,2,4,8,16); return ++$v; }
      i don't know why i was compelled to post that, but i knew one could reduce the repition and possibly obfuscate the code a little with some obviously useless uses of map doing things it wasn't meant to do...
      my $0.02;

      jynx

        #or perhaps $w=32; $v |= $v>>($w>>=1) while $w;
Re: Power of two round up.
by myocom (Deacon) on Dec 15, 2000 at 23:54 UTC
    More TIMTOWTDI:
    for my $foo (1..210) { print "$foo ",dec2bin($foo)," binrounded is ",binround($foo),"\n"; } sub binround { my $bin = dec2bin(shift); my $mod = 0; $mod = 1 if (split('1','0'.$bin.'0') == 2); return '1' . ('0' x (length($bin)-$mod)); } sub dec2bin { my $str = unpack("B32", pack("N", shift)); $str =~ s/^0+(?=\d)//; return $str; }

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (8)
As of 2014-04-16 11:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (424 votes), past polls