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