CODEWITHSUNDEEP
php
Kartik
Kartik

Reputation: 9853

Finding if a number is a power of 2

Just out of curiosity, how can you tell if a number x is a power of two (x = 2^n) without using recursion.

Thanks

Upvotes: 22

Views: 9543

Answers (9)

Suresh Hemal
Suresh Hemal

Reputation: 40

I tried to implement the same thing without bitwise operators. Finally, I ended up with

return (fmod(log($x, 2), 1) === 0.00)

(In PHP)

Upvotes: 0

ListenSoftware Louise Ai Agent
ListenSoftware Louise Ai Agent

Reputation: 4243

use mod 2 to determine if a number is a power of 2

def is_power_of_2(n):
    if n == 0:
        return False
    while n % 2 == 0:
        n = n / 2
    return n == 1

Upvotes: 0

Chris Wheeler
Chris Wheeler

Reputation: 1716

The top answer:

($x & ($x - 1)) == 0

seemed to have issues with larger numbers for me, this works well for larger numbers using the same logic but with GMP:

gmp_strval(gmp_and($x, gmp_sub($x, 1))) == 0

Upvotes: 0

Stranger
Stranger

Reputation: 10611

In a binary equivalent of any decimal number which is a power of two will have only one occurrence of 1 in its binary equivalent.

<?php
    $number = 4096;
    $bin = decbin($number);
    if ($number != 1 && substr_count($bin,1) == 1) {
        echo "Yes";
    } else {
        echo "No";
    }
?>

Upvotes: 1

Brent
Brent

Reputation: 15

Math.log(x)/Math.log(2) == Math.floor(Math.log(x)/Math.log(2))

Upvotes: -2

Artefacto
Artefacto

Reputation: 97835

For completeness, if the number is a float, you can test if it's a power of two by chacking if the mantissa is all zeros:

<?php
$number = 1.2379400392853803e27;
$d = unpack("h*", pack("d", $number)); $d = reset($d);
$isPowerOfTwo = substr($d, 0, 13) == "0000000000000";
var_dump($isPowerOfTwo); // bool(true)

Exercise for the reader: corner cases and big-endian machines.

Upvotes: 2

ircmaxell
ircmaxell

Reputation: 165201

If it's a power of 2? Well, one way is to convert it to binary, and verify the presence of only 1 1...:

$bin = decbin($number);
if (preg_match('/^0*10*$/', $bin)) {
    //Even Power Of 2
}

Upvotes: 3

Ned Batchelder
Ned Batchelder

Reputation: 375604

Subtract 1 from the number, then and it with the original number. If the result is zero, it was a power of two.

if (((n-1) & n) == 0) {
    // power of two!
}

(sorry, my PHP is rusty...)

Upvotes: 10

dan04
dan04

Reputation: 91015

One way is to use bitwise AND. If a number $x is a power of two (e.g., 8=1000), it will have no bits in common with its predecessor (7=0111). So you can write:

($x & ($x - 1)) == 0

Note: This will give a false positive for $x == 0.

Upvotes: 54

Related Questions