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

larryk has asked for the wisdom of the Perl Monks concerning the following question:

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% -- [download]	[reply] [d/l]
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% -- [download]	[reply] [d/l]
Re: Re: How can I tell if a number is a power of 2? by Juerd (Abbot) on Jan 29, 2002 at 02:15 UTC
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% -- [download] `2;0 juerd@ouranos:~$ perl -e'undef christmas' Segmentation fault 2;139 juerd@ouranos:~$` [download]	[reply] [d/l] [select]
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 }` [download] 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; }` [download]	[reply] [d/l] [select]
(tye)Re: How can I tell if a number is a power of 2? by tye (Sage) on Jan 29, 2002 at 02:00 UTC
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` [download] 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` [download] which has the advantage of catching negative-powers of 2 and negative powers-of-2. (: - tye (but my friends call me "Tye")	[reply] [d/l] [select]
Re: How can I tell if a number is a power of 2? by talexb (Chancellor) 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;} }` [download]	[reply] [d/l]
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; }` [download]	[reply] [d/l]
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 ... ) }` [download]	[reply] [d/l]
Re: Re: How can I tell if a number is a power of 2? by Cine (Friar) on Jan 29, 2002 at 00:25 UTC
`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.` [download] T I M T O W T D I Edit by tye to replace PRE to CODE around long line(s)	[reply] [d/l]
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; }` [download]	[reply] [d/l]
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 }` [download] --Dave	[reply] [d/l]
Re: How can I tell if a number is a power of 2? by archen (Pilgrim) on Jan 28, 2002 at 23:12 UTC
err, I have no idea how this would benchmark, but couldn't you do `return ! $number % 2;` [download] You'd pay a penalty in the calculation, but by the time you get done with sprintf, pattern matching, and a conditional I think the gap would be a lot closer. Originally posted as a Categorized Answer.	[reply] [d/l]
Re: Re: How can I tell if a number is a power of 2? by VSarkiss (Monsignor) on Jan 28, 2002 at 23:16 UTC
Oops! You're testing whether `$number` is odd or even, not whether it's a power of 2.	[reply] [d/l]


Perl Monk, Perl Meditation
	PerlMonks