Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
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
Replies are listed 'Best First'.
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 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 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 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 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 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 cooling their heels in the Monastery: (9)
As of 2015-07-08 04:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (94 votes), past polls