Next/Prev power of 2

Here is a rather evil way to quickly compute the closest powers of 2 to a number.

First, figure out which bits represent the mantissa in your native floating point format. Then you can zero out all of the bits in the mantissa (which doesn't include the highest bit) and get the closest previous power of 2.

Getting the closest next power of 2 is a bit trickier.

Inspired by a CB question from BrowserUk and my previous (tye)Re: How can I tell if a number is a power of 2?.

Sample output:

0 == 0 == 0
1 <= 1 <= 1
2 <= 2 <= 2
2 <= 3 <= 4
4 <= 4 <= 4
4 <= 5 <= 8
16384 <= 32000 <= 32768
8589934592 <= 10000000000 <= 17179869184
-2 >= -2 >= -2
-2 >= -3 >= -4
0.0625 <= .1 <= 0.125
0.0078125 <= .01 <= 0.015625
-0.0009765625 >= -.001 >= -0.001953125
5.61779104644474e+306 <= 1e307 <= 1.12355820928895e+307
8.98846567431158e+307 <= 1e308 <= 1.#INF
8.90029543402881e-308 <= 1e-307 <= 1.78005908680576e-307
[download]

(updated)

#!/usr/bin/perl -w
use strict;

my $mant;
BEGIN {
    my $max= 2;
    $max *= 2   until  2*$max+1 == 2*$max;
    $mant= pack("d",$max) ^ pack("d",2*$max-1);
}

sub prevPower2 {
    my( $n )= @_;
    return  unpack "d", ~$mant & pack "d", $n;
}

sub nextPower2 {
    my( $n )= @_;
    my $p= prevPower2( $n );
    $p *= 2   if  $p != $n;
    return  $p;
}

while(  <>  ) {
    chomp;
    my $dir= (qw( < = > ))[ 1 + (0<=>$_) ];
    print prevPower2($_), " $dir= $_ $dir= ", nextPower2($_), $/;
}
[download]

Comment on Next/Prev power of 2 Select or Download Code

Replies are listed 'Best First'.
Re: Next/Prev power of 2 by jmcnamara (Monsignor) on Dec 13, 2002 at 14:09 UTC
That's very nice. ++ Here is a less elegant, and slower, solution that uses some of the POSIX functions: `#!/usr/bin/perl -wl use strict; use POSIX qw(frexp ldexp); sub prev_power2 { return 0 if $_[0] == 0; my $num = $_[0]; my ($mant, $exp) = frexp($num); my $sign = $mant < 0 ? -1 : 1; return ldexp(0.5 $sign, $exp); } sub next_power2 { my $num = $_[0]; my $prev = prev_power2($num); my $next = $prev; $next = $prev 2 if $prev != $num; return $next; }` [download] The following seems to be faster than both of the above. It doesn't handle numbers less than 1 but that could be fixed. `sub prev_power2 { return 2 ** int log($_[0]) / log 2; }` [download] Finally, how not to do it: Power Twool -- John.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Next/Prev power of 2
by jmcnamara (Monsignor) on Dec 13, 2002 at 14:09 UTC

Here is a less elegant, and slower, solution that uses some of the POSIX functions:

    #!/usr/bin/perl -wl

    use strict;
    use POSIX qw(frexp ldexp);


    sub prev_power2 {

        return 0 if $_[0] == 0;
        my $num          = $_[0];
        my ($mant, $exp) = frexp($num);
        my $sign         = $mant < 0 ? -1 : 1;

        return ldexp(0.5 *$sign, $exp);
    }


    sub next_power2 {

        my $num  = $_[0];
        my $prev = prev_power2($num);
        my $next = $prev;

        $next = $prev *2 if $prev != $num;
        return $next;
    }
[download]

The following seems to be faster than both of the above. It doesn't handle numbers less than 1 but that could be fixed.

    sub prev_power2 {
        return 2 ** int log($_[0]) / log 2;
    }
[download]

Finally, how not to do it: Power Twool

--
John.

[reply]
[d/l]
[select]