Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
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 perusing the Monastery: (6)
As of 2014-07-25 23:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (175 votes), past polls