Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Power of two round up.

by boo_radley (Parson)
on Dec 15, 2000 at 22:59 UTC ( [id://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; }

Replies are listed 'Best First'.
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 (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 c-alpha (Novice) on Aug 26, 2023 at 13:59 UTC

    With a little help from POSIX, and remembering some basics about polyadic number systems, i.e. with the help of the natural logarithm, an IMHO straightforward implementation can be made:

    use POSIX qw(ceil); sub powround { my ( $x, $base ) = @_; return ( $base ** ceil(log($x)/log($base))); }

    That is, ln(a) / ln(b) gives you the number of digits needed to represent the number a relative to the base b (and ln() is the natural logarithm, i.e. to the base e (Euler's number)).

    Then round that up to the next greater or equal integer (POSIX::ceil), and exponentiate the base with it. Voilą, you have the next greater or equal power of the base.

    p.s.: using `POSIX::ceil` covers all corner cases, whereas using `int(...) + 1` as suggested in previous responses, does not.

      ...and ln() is the natural logarithm

      Note that it doesn't have to be the natural logarithm. You can use a log to any base.
      D:\>perl -MPOSIX="log10,log2" -le "$r1=log(1234)/log(2);$r2=log10(1234 +)/log10(2);$r3=log2(1234)/log2(2);print $r1; print $r2; print $r3;" 10.269126679149417887862906163471 10.269126679149417887862906163471 10.269126679149417887862906163471
      Cheers,
      Rob

        You can use a log to any base, indeed, for as long as you use the same base for both dividend and divisor.

        And, coincidentally, the log to the base Euler's number is the only one one available as part of core Perl. So as to minimize the readers' confusion, I opted to using that.

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; }
Re: Power of two round up.
by jimav (Sexton) on Aug 25, 2023 at 17:55 UTC
    1 << length(sprintf("%b", $input))

    Not fast, of course, but perfectly fine when called only once such as for a new constant (or other inlineable subs)

    use Some::Other::Module 'SOM_FLAGS_MAX'; use constant MY_FLAGS_MIN => (1<<length(sprintf("%b", SOM_FLAGS_MAX));