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\$
  • 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
  • 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\$ – 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
  • \$\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\$ – Toby Speight Feb 20 at 10:53
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

| improve this answer | |
\$\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
  • 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 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.

| improve this answer | |
\$\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 Feb 19 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 at 17:41
  • \$\begingroup\$ Please explain how this is a review. If it's not a review, it isn't "satisfactory" here. \$\endgroup\$ – Toby Speight Feb 19 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 at 18:17
  • \$\begingroup\$ Just because the other answers are poor doesn't mean that more poor answers are welcome. \$\endgroup\$ – Toby Speight Feb 20 at 8:45

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.