Find out whether number is of Power of Two

Question

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: 2⁰ = 1

Example 2:

Input: 16

Output: true

Explanation: 2⁴ = 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;
};

Answer 1

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

Answer 2

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.