Perl-Sensitive Sunglasses PerlMonks

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

by larryk (Friar)
 on Jan 28, 2002 at 21:37 UTC 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?

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 ;-) (Prior) 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;

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
```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

Create A New User
Node Status?
node history
Node Type: perlquestion [id://142122]
Approved by root
help
Chatterbox?
 [robby_dobby]: Corion: Yes, I know it's fun. We met at LPW last year. First time volunteer and all, it was fun! :-)

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (8)
As of 2018-04-19 12:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (73 votes). Check out past polls.

Notices?