1
\$\begingroup\$

The task

is taken from leetcode

Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1

Output: true

Explanation: 20 = 1

Example 2:

Input: 16

Output: true

Explanation: 24 = 16

Example 3:

Input: 218

Output: false

My solution

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfTwo = function(n) {
  if (n <= 0 ) { return false; }
  if (n <= 2) { return true; }
  let num = n;
  do {
    const x = num / 2;
    if ((x | 0) !== x) { return false; }
    if (x === 2) { return true; }
    num = x;
  } while(num);
  return false;
};
\$\endgroup\$
  • 1
    \$\begingroup\$ The constant time solution is to return n & (n - 1) === 0. Try to understand how it works. \$\endgroup\$ – vnp May 22 at 23:28
  • \$\begingroup\$ @vnp: fails for n=0. @op: any JavaScript solution using bitwise ops on the entire input will fail for many values smaller Number.MAX_SAFE_INTEGER (2^53 - 1) because those operations coerce inputs to 32-bit signed values. \$\endgroup\$ – Oh My Goodness May 23 at 1:29
  • \$\begingroup\$ Are you not allow to use the Math library? \$\endgroup\$ – dwjohnston May 23 at 8:15
  • \$\begingroup\$ @dwjohnston wouldn't that be too easy? \$\endgroup\$ – thadeuszlay May 23 at 21:42
2
\$\begingroup\$

I think this code should work and is about the fastest way i can think to do it.

    var ispoweroftwo = function(i)
    {
        var ret = (i == 1);
        var n = i;
        if(n > 0)
        {
            do
            {
                if((n & 1) == n) //divided by an exponent of 2 is exact
                {
                    ret = true;
                    break;
                }
                else if((n & 1) == 1) 
                {
                    break;
                }
            }while ((n >>= 1) > 0);
        }
        return ret;
    }
\$\endgroup\$
  • \$\begingroup\$ right shift is equivalent to dividing by 2, but runs a lot faster than division. This code should give excellent performance, and reads fairly cleanly without the hardcoded checks for 2 or 1. I just check if it is either an exact exponent of 2 or an odd number that is not 1. \$\endgroup\$ – justjoshin May 23 at 4:34
  • \$\begingroup\$ aplogies, adapted from c#, will edit \$\endgroup\$ – justjoshin May 23 at 6:01
  • \$\begingroup\$ should work now \$\endgroup\$ – justjoshin May 23 at 6:05
  • \$\begingroup\$ if((n & 1) == n) is true only for 0 and 1, with 0 excluded by the loop condition. Why not write just if (n==1)? And why copy i to n? \$\endgroup\$ – Oh My Goodness May 23 at 7:00
  • \$\begingroup\$ i haven't written much javascript in a while :-). couldn't remember off the top of my head if it was a pass by ref or pass by value as default language. You don't need to make a local copy of the passed in variable. The first loop breaking check can be replaced with a check for equality with 1. \$\endgroup\$ – justjoshin May 23 at 7:19
1
\$\begingroup\$

I mean, I would use a library to do this. Namely, Math.log2

function isPowerOfTwo(n) {
  return Math.log2(n) % 1 === 0;
}

console.log(isPowerOfTwo(3)); //false
console.log(isPowerOfTwo(4)); //true
console.log(isPowerOfTwo(7)); //false
console.log(isPowerOfTwo(8)); //true
console.log(isPowerOfTwo(-1));//false

\$\endgroup\$
  • 1
    \$\begingroup\$ So tempting to try to resurrect the old "-1: not enough jquery" meme... \$\endgroup\$ – Jerry Coffin May 23 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.