SPUG: Cool power-of-2 trick
Michael R. Wolf
MichaelRWolf at att.net
Thu Jan 20 15:05:44 PST 2005
At 02:42 PM 1/20/2005, Aaron W. West wrote:
>I wonder if there's a quick way to find the smallest power of two equal to
>or greater than a given number.
Yes, for some definition of 'quick'. It's iterative, not a constant order.
Michael
#! /usr/bin/perl -w
sub next_power_of_2 {
my $num = shift;
my $ones = 0;
while ($num) {
$ones |= $num;
$num >>= 1;
}
return $ones+1;
}
for my $i (0 .. 2<<4) {
printf "%2d is less than this power of two %3d\n",
$i, next_power_of_2($i);
}
0 is less than this power of two 1
1 is less than this power of two 2
2 is less than this power of two 4
3 is less than this power of two 4
4 is less than this power of two 8
5 is less than this power of two 8
6 is less than this power of two 8
7 is less than this power of two 8
8 is less than this power of two 16
9 is less than this power of two 16
10 is less than this power of two 16
11 is less than this power of two 16
12 is less than this power of two 16
13 is less than this power of two 16
14 is less than this power of two 16
15 is less than this power of two 16
16 is less than this power of two 32
17 is less than this power of two 32
18 is less than this power of two 32
19 is less than this power of two 32
20 is less than this power of two 32
21 is less than this power of two 32
22 is less than this power of two 32
23 is less than this power of two 32
24 is less than this power of two 32
25 is less than this power of two 32
26 is less than this power of two 32
27 is less than this power of two 32
28 is less than this power of two 32
29 is less than this power of two 32
30 is less than this power of two 32
31 is less than this power of two 32
32 is less than this power of two 64
Michael R. Wolf
All mammals learn by playing!
MichaelRWolf at att.net
More information about the spug-list
mailing list