Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

How can I tell if a number is a power of 2?

by larryk (Friar)
on Jan 28, 2002 at 21:37 UTC ( #142122=perlquestion: print w/ replies, xml ) Need Help??
larryk has asked for the wisdom of the Perl Monks concerning the following question:

I understand the binary representation of such a number will be a 1 with zero or more trailing 0s so with that in mind I rather sheepishly offer the following:
sub is_power_of_2 { my $number = shift; sprintf('%b',$number) =~ /^10*$/ ? 1 : 0; }
What is the most efficient way to shift that 1 to the other end so I can compare the value to 1 instead of using this horrible regex. Or is there a quicker way?

Comment on How can I tell if a number is a power of 2?
Download Code
Re: How can I tell if a number is a power of 2?
by larryk (Friar) on Jan 28, 2002 at 22:31 UTC
    After a session in the CB:
    #!perl use strict; use warnings; use Benchmark qw/cmpthese/; sub one { my $number = shift; sprintf('%b',$number) =~ /^10*$/ ? 1 : 0; } sub two { my $number = shift; 1 == reverse sprintf('%b',$number) ? 1 : 0; } sub three { my $number = shift; 1 == substr(sprintf('%b',$number),0,1) ? 1 : 0; } my %h = map { $_ ** 2 => 1 } (0..63); sub jeffa { my $number = shift; exists $h{$number} ? 1 : 0; } sub tye { my $x = shift; 0 == ( $x & ($x-1) ) ? 1 : 0; } my %h2 = (); @h2{map $_**2,0..63}; # word of mouth: by tilly sub tilly { # really just another impl. of jeffa's lookup my $number = shift; exists $h2{$number} ? 1 : 0; } cmpthese( -5, { one => q!one(rand 1000000)!, two => q!two(rand 1000000)!, three => q!three(rand 1000000)!, tye => q!tye(rand 1000000)!, jeffa => q!jeffa(rand 1000000)!, tilly => q!tilly(rand 1000000)!, } ); __END__ Benchmark: running jeffa, one, three, tilly, two, tye, each for at lea +st 5 CPU seconds... jeffa: 6 wallclock secs ( 5.01 usr + 0.00 sys = 5.01 CPU) @ 62 +422.92/s (n=312614) one: 5 wallclock secs ( 5.14 usr + 0.00 sys = 5.14 CPU) @ 11 +9667.70/s (n=614733) three: 5 wallclock secs ( 5.25 usr + 0.00 sys = 5.25 CPU) @ 90 +412.81/s (n=474396) tilly: 6 wallclock secs ( 5.01 usr + 0.00 sys = 5.01 CPU) @ 63 +202.16/s (n=316390) two: 6 wallclock secs ( 5.14 usr + 0.00 sys = 5.14 CPU) @ 11 +9035.80/s (n=611725) tye: 6 wallclock secs ( 5.25 usr + 0.00 sys = 5.25 CPU) @ 21 +0491.04/s (n=1104657) Rate jeffa tilly three two one tye jeffa 62423/s -- -1% -31% -48% -48% -70% tilly 63202/s 1% -- -30% -47% -47% -70% three 90413/s 45% 43% -- -24% -24% -57% two 119036/s 91% 88% 32% -- -1% -43% one 119668/s 92% 89% 32% 1% -- -43% tye 210491/s 237% 233% 133% 77% 76% --
Re: How can I tell if a number is a power of 2?
by talexb (Canon) on Jan 28, 2002 at 22:43 UTC
    There are a bunch of ways of solving this .. you could try just running through the powers of two:
    my$a=256; for(my$b=1;$b<1E9;$b*=2) { if($a==$b){print'Match!';last;} }
Re: How can I tell if a number is a power of 2?
by larryk (Friar) on Jan 28, 2002 at 22:52 UTC
    Of course implementation is everything:
    #!perl use strict; use warnings; use Benchmark qw/cmpthese/; sub tye { my $x = shift; 0 == ( $x & ($x-1) ) ? 1 : 0; } sub tye2 { my $x = shift; !( $x & ($x-1) ); } cmpthese( -5, { tye => q!tye(rand 1000000)!, tye2 => q!tye2(rand 1000000)!, } ); __END__ Benchmark: running tye, tye2, each for at least 5 CPU seconds... tye : 6 wallclock secs ( 5.07 usr + 0.00 sys = 5.07 CPU) @ 200612 +.27/s (n=1016703) tye2: 6 wallclock secs ( 5.02 usr + 0.00 sys = 5.02 CPU) @ 225545 +.83/s (n=1131789) Rate tye tye2 tye 200612/s -- -11% tye2 225546/s 12% --
      And just because implementation is everything:
      #!/usr/bin/perl use strict; use warnings; use Benchmark qw/cmpthese/; sub tye2 { my $x = shift; !( $x & ($x-1) ); } sub tye3 { my ($x) = @_; !( $x & ($x-1) ); } sub tye4 { !( $_[0] & ($_[0] - 1) ); } cmpthese( -5, { tye2 => q!tye2(rand 1000000)!, tye3 => q!tye3(rand 1000000)!, tye4 => q!tye4(rand 1000000)!, } ); __END__ tye2:6wcs (5.30usr + 0.01sys = 5.31CPU) @ 384813.56/s (n=2043360) tye3:6wcs (5.07usr + 0.00sys = 5.07CPU) @ 381046.15/s (n=1931904) tye4:5wcs (5.42usr + 0.00sys = 5.42CPU) @ 493005.17/s (n=2672088) Rate tye3 tye2 tye4 tye3 381046/s -- -1% -23% tye2 384814/s 1% -- -22% tye4 493005/s 29% 28% --

      2;0 juerd@ouranos:~$ perl -e'undef christmas' Segmentation fault 2;139 juerd@ouranos:~$

Re: How can I tell if a number is a power of 2?
by dws (Chancellor) on Jan 28, 2002 at 23:27 UTC
    What is the most efficient way to shift that 1 to the other end so I can compare the value to 1 instead of using this horrible regex. Or is there a quicker way?

    I might try table lookup.

    sub is_power_of_2 { my $n = shift; 1 == grep { $_ == $n } ( 1 2 4 8 ... ) }
      if n is a power of two, then n = 2^x => lg n = x*lg 2 => lg n/lg 2 = x => lg n = x thus lg n is the power of 2 of your number. But usually only log10 and + natural log is avail, but lg x = log x/ lg e.


      T I M T O W T D I

      Edit by tye to replace PRE to CODE around long line(s)

Re: How can I tell if a number is a power of 2?
by trammell (Priest) on Jan 29, 2002 at 00:19 UTC
    sub ispow2 { my $i = shift; while ($i) { if ($i % 2) { return ($i == 1) ? 1 : 0 } $i >>= 1; } return 0; }
Re: How can I tell if a number is a power of 2?
by cLive ;-) (Parson) on Jan 29, 2002 at 00:25 UTC
    Obviously no mathematicians in the house :)
    sub is_power_of_2 { return 0 unless $_[0]>0; # to avoid log error log($_[0])/log(2) - int(log($_[0])/log(2)) ? 0 : 1 }
    cLive ;-)

    Update: - Cine (not linked because of very irritating JS on home node) proves me wrong while I'm typing up :)

    Update: - Damn you tye... This falls down as far as computing accuracy goes for 2 to the power of 29, 31, 39, 47 and probably a few more. Where's that posix math module when you need it :)

    Ah well, here's another:

    sub is_power_of_2 { local $_ = $_[0]; $_/=2 while ($_ > 1); return if ($_ - int($_)); 1; }

      Well, if you could portably ask whether the mantissa of the number was represented with all 0 bits (since the leading 1 bit is implied and so doesn't appear)...

      #!/usr/bin/perl -w use strict; my $mask; BEGIN { my $max= 2; $max *= 2 until 2*$max+1 == 2*$max; $mask= pack("d",$max) ^ pack("d",2*$max-1); } sub power2 { my( $n )= @_; return if ! $n; return( ( $mask & pack "d", $n ) !~ /[^\0]/ ); } for( split " ", do { local($/); <DATA> } ) { print "$_: ", power2($_)?1:0, "\n"; } __END__ 0 1 2 3 4 5 6 7 8 9 0.5 0.2 0.25 0.125 -1 -2 -3 -.25
      produces
      0: 0 1: 1 2: 1 3: 0 4: 1 5: 0 6: 0 7: 0 8: 1 9: 0 0.5: 1 0.2: 0 0.25: 1 0.125: 1 -1: 1 -2: 1 -3: 0 -.25: 1
      which has the advantage of catching negative-powers of 2 and negative powers-of-2. (:

              - tye (but my friends call me "Tye")
Re: How can I tell if a number is a power of 2?
by c-era (Curate) on Jan 29, 2002 at 01:13 UTC
    How about this one?
    sub is_power_of_2{ $num = shift; $num2 = 1; while ($num>$num2){ $num2=$num2<<1; } return ($num^$num2)?0:1; }
Re: How can I tell if a number is a power of 2?
by dpuu (Chaplain) on Dec 12, 2002 at 20:49 UTC
    The answers given so far all seem overly complex. If the input is an integer less than 2**32 then simply:
    sub is_power_of_two { not $_[0] & $_[0]-1 }
    --Dave

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://142122]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2014-09-03 00:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (34 votes), past polls