CODEWITHSUNDEEP
javascript
Marco V
Marco V

Reputation: 2623

What is the best way to determine if a given number is a power of two?

Is there a more effective way to return true if n is a power of two or false if not?

function isPowerOfTwo(n) {
  return Math.pow(2, Math.round(Math.log(n) / Math.log(2)));
}

Upvotes: 19

Views: 26599

Answers (8)

Hans Brende
Hans Brende

Reputation: 8577

Here's a version that works for every power of 2 (not just 32-bit integers), without using log or log2 (neither of which ECMAScript actually guarantees will return the correct result).

const isPowerOf2 = (n) => 
    n >= 2.2250738585072014e-308 ? n - n * 0.9999999999999999 + n === n : 
    n > 0 && isPowerOf2(n / 5e-324);

This function takes advantage of the fact that powers of 2 are the only numbers for which the distance to the next larger number is double the distance to the next smaller number. And by extension, since rounding ties are broken towards the even significand, they are the only numbers for which adding the smaller distance has no effect.

Upvotes: 0

Will Ware
Will Ware

Reputation: 505

function PowerOfTwo(n){
  // Exercise for reader: confirm that n is an integer
  return (n !== 0) && (n & (n - 1)) === 0;
}
console.log(PowerOfTwo(3))
console.log(PowerOfTwo(4))

Upvotes: 2

ASHISH R
ASHISH R

Reputation: 4189

/**
 * @param {number} n
 * @return {boolean}
 */
const isPowerOfTwo = function(n) {
    if(n == 0) return false;

    while(n % 2 == 0){
        n = n/2
    }
    return n === 1
};

Upvotes: 3

thefourtheye
thefourtheye

Reputation: 239483

Source: Bit twiddling Hacks,

function powerOf2(v) {
    return v && !(v & (v - 1));
}

You just bitwise AND the previous number with the current number. If the result is falsy, then it is a power of 2.

The explanation is in this answer.

Note:

  • This will not be 100% true for programming, mathematical, [also read 'interviewing']. Some edge cases not handled by this are decimals (0.1, 0.2, 0.8…) or zero values (0, 0.0, …)

Upvotes: 30

le_m
le_m

Reputation: 20228

Making use of ES6's Math.clz32(n) to count leading zeros of a 32-bit integer from 1 to 2³² - 1:

function isPowerOf2(n) {
  return Math.clz32(n) < Math.clz32(n - 1);
}

Upvotes: 2

Joseph Palermo
Joseph Palermo

Reputation: 387

A number is a power of 2 if and only if log base 2 of that number is whole. The function below computes whether or not that is true:

function powerOfTwo(n){
    // Compute log base 2 of n using a quotient of natural logs
    var log_n = Math.log(n)/Math.log(2);
    // Round off any decimal component
    var log_n_floor = Math.floor(log_n);
    // The function returns true if and only if log_n is a whole number
    return log_n - log_n_floor == 0; 
}

Upvotes: 3

iam-decoder
iam-decoder

Reputation: 2564

Using bitwise operators, this is by far the best way in terms of efficiency and cleanliness of your code:

function PowerofTwo(n){
    return ((x != 0) && !(x & (x - 1)));
}

what it does is checks the bits that make up the number, i.e. 8 looks like this:

1 0 0 0

x-1 or 7 in this case looks like this

0 1 1 1

when the bitwise operator & is used it invokes an && on each bit of the number (thus 1 & 1 = 1, 1 & 0 = 0, 0 & 1 = 0, 0 & 0 = 1):

 1 0 0 0
-0 1 1 1
=========
 0 0 0 0

since the number turns into an exact 0 (or false when evaluted as a boolean) using the ! flag will return the correct answer

if you were to do this with a number like 7 it would look like this:

 0 1 1 1
-0 1 1 0
=========
 1 1 1 0

returning a number greater than zero causing the ! flag to take over and give the correct answer.

Upvotes: 3

Josh Beam
Josh Beam

Reputation: 19772

You can actually use ECMAScript5 Math.log:

function powerOfTwo(x) {
    return (Math.log(x)/Math.log(2)) % 1 === 0;
}

Remember, in math, to get a logarithm with an arbitrary base, you can just divide log10 of the operand (x in this case) by log10 of the base. And then to see if the number is a regular integer (and not a floating point), just check if the remainder is 0 by using the modulus % operator.

In ECMAScript6 you can do something like this:

function powerOfTwo(x) {
    return Math.log2(x) % 1 === 0;
}

See the MDN docs for Math.log2.

Upvotes: 39

Related Questions