4
\$\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\$
5
  • 2
    \$\begingroup\$ The constant time solution is to return n & (n - 1) === 0. Try to understand how it works. \$\endgroup\$
    – vnp
    May 22, 2019 at 23:28
  • 2
    \$\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\$ May 23, 2019 at 1:29
  • \$\begingroup\$ Are you not allow to use the Math library? \$\endgroup\$
    – dwjohnston
    May 23, 2019 at 8:15
  • \$\begingroup\$ @dwjohnston wouldn't that be too easy? \$\endgroup\$ May 23, 2019 at 21:42
  • \$\begingroup\$ @OhMyGoodness, that's a good point, but we can use the constant-time solution as a basis for code that works with larger values (by splitting width-wise into portions, of which exactly one must be a power of two and the others exactly zero). \$\endgroup\$ Feb 20, 2020 at 10:53

2 Answers 2

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\$
2
  • 1
    \$\begingroup\$ So tempting to try to resurrect the old "-1: not enough jquery" meme... \$\endgroup\$ May 23, 2019 at 16:46
  • 1
    \$\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
    Feb 20, 2020 at 2:20
-1
\$\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\$
5
  • \$\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\$ Feb 19, 2020 at 16:41
  • \$\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
    Feb 19, 2020 at 17:41
  • \$\begingroup\$ Please explain how this is a review. If it's not a review, it isn't "satisfactory" here. \$\endgroup\$ Feb 19, 2020 at 17:45
  • \$\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
    Feb 19, 2020 at 18:17
  • \$\begingroup\$ Just because the other answers are poor doesn't mean that more poor answers are welcome. \$\endgroup\$ Feb 20, 2020 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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