CODEWITHSUNDEEP
javascriptmathbit-manipulation
Lance Pollard
Lance Pollard

Reputation: 79440

How to get the exponent "x" (2 to the power of "x") without using Math.log in JavaScript?

I have this so far (which is all bitwise, not using Math functions):

function nextPowerOf2(n) {  
  if (n && !(n & (n - 1))) {
    return n
  }

  let p = 1
  while (p < n) {
    p <<= 1
  }
  
  return p  
}

To get the exponent though, I have to do this:

const exp = Math.log2(nextPowerOf2(val))

Is there any way to do this without Math.log, using more primitive operations? Which way is better performing?

Upvotes: 0

Views: 95

Answers (2)

Anton
Anton

Reputation: 2713

We can count number of bits in a number - that will be log2(nextPowerOf2):

const log2ofNextPowerOf2 = (x) => {
  if (!x) return 0;
  let c = 0, b = 0;
  while (x > 0) {
    c++; b += x & 1;
    x = x >> 1;
  }
  return b == 1 ? c - 1 : c;
}

// test it:
[0, 1, 2, 3, 4, 5, 8, 100].forEach(n => console.log(n, '=>', log2ofNextPowerOf2(n)));

Compare this to your original function:

function nextPowerOf2(n) {
  if (n && !(n & (n - 1))) {
    return n
  }
  let p = 1
  while (p < n) {
    p <<= 1
  }

  return p
}

// test it:
[0, 1, 2, 3, 4, 5, 8, 100].forEach(n => console.log(n, '=>', Math.log2(nextPowerOf2(n))));

Upvotes: 2

Sei4or
Sei4or

Reputation: 68

In my experience Math.log2 is pretty performant, especially when compared to other options using bitwise and even lookup tables.

If you would like to see how it could be done with bitwise here is a great resource: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog

Here is an example adapted for JS from C++ (be careful of numbers past Number.MAX_SAFE_INTEGER) which is ~59% slower

function log2(v) {
    let b = [0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000];
    let S = [1, 2, 4, 8, 16, 32];
    let i;

    let r = 0;
    for (i = 5; i >= 0; i--){
        if (v & b[i]) {
            v >>= S[i];
            r |= S[i];
        } 
    }

    return r;
}

log2(nextPowerOf2(348209348));

Upvotes: 1

Related Questions