2
\$\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\$
  • 2
    \$\begingroup\$ The constant time solution is to return n & (n - 1) === 0. Try to understand how it works. \$\endgroup\$ – vnp May 22 '19 at 23:28
  • 1
    \$\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 '19 at 1:29
  • \$\begingroup\$ Are you not allow to use the Math library? \$\endgroup\$ – dwjohnston May 23 '19 at 8:15
  • \$\begingroup\$ @dwjohnston wouldn't that be too easy? \$\endgroup\$ – thadeuszlay May 23 '19 at 21:42
1
\$\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 '19 at 4:34
  • \$\begingroup\$ aplogies, adapted from c#, will edit \$\endgroup\$ – justjoshin May 23 '19 at 6:01
  • \$\begingroup\$ should work now \$\endgroup\$ – justjoshin May 23 '19 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 '19 at 7:00
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight 13 hours ago
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 '19 at 16:46
  • \$\begingroup\$ I know this is an answer from a bit ago, but the question has garnered some attention. while this might be some good advice for production code, it appears that the OP is for a challenge and being a challenge your answer would circumvent the challenge itself. \$\endgroup\$ – Malachi 4 hours ago
-2
\$\begingroup\$

I realize that this is an old question, but I though I'd provide my approach anyway.

What you really want to do, is count the number of active or set bits, as a power of two is always represented as a single bit.

Now, I'm not much for javascript, so this is semi pseudo/c code, but I do believe the operators are more or less the same.

bool isPowerOf2( uint64_t b )
{
    b = ((b >>  1) & 0x5555555555555555) + (b & 0x5555555555555555);
    b = ((b >>  2) & 0x3333333333333333) + (b & 0x3333333333333333); 
    b = ((b >>  4) & 0x0f0f0f0f0f0f0f0f) + (b & 0x0f0f0f0f0f0f0f0f); 
    b = ((b >>  8) & 0x00ff00ff00ff00ff) + (b & 0x00ff00ff00ff00ff); 
    b = ((b >> 16) & 0x0000ffff0000ffff) + (b & 0x0000ffff0000ffff);
    b = ((b >> 32) & 0x00000000ffffffff) + (b & 0x00000000ffffffff);
    return (b==1);
}

Now this is able to handle 64 bit, but if you only need 32 or less, it can be adapted accordingly. It may look complicated, but it really isn't. What you do is separate the bit up in to pairs and add them. First you add bit 0 with bit 1, bit 2 with bit 3, etc. Then you do the same again, adding bit 0-1 with 2-3, 4-5 with6-7, and so on.

With the exception of some architecture depended instructions, like GCCs __builin_popcount, I know of no way that is more efficient, but then again, if you're coding in javascript, that is probably not a priority, and you may want to use another method. Just know that what you really want to do, is count bits.

\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight 14 hours ago
  • \$\begingroup\$ I shall not. To me this is perfectly satisfactory. If you, upon further review,still disagree, you may delete it, and I shall refrain from posting, anything, in the future. \$\endgroup\$ – Zacariaz 13 hours ago
  • \$\begingroup\$ Please explain how this is a review. If it's not a review, it isn't "satisfactory" here. \$\endgroup\$ – Toby Speight 13 hours ago
  • \$\begingroup\$ It's a matter of definitions, and I'm not getting into a debate here, but you might want to consider how the other answers are reviews. A problem was posed, two different solutions was suggested and I offered a third, hoping that it might help people to "learn". Don't like it? Fine by me. Bon voyage. \$\endgroup\$ – Zacariaz 12 hours ago

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.