Minimum bits required to represent a natural number

Question

What is the most performative way to find the minimum number of bits needed to represent a natural number (i.e. no signal) in Javascript? There is a way to do without using loops?

The code below for example works for every integer between 0 and 2^30 - 1 (infinite loop if it is larger than that):

var x = 9001;
var bits = 1;
while ( x >= (1 << bits) )
    bits++;

And this one works until 2^53 (the largest representable integer guaranteed without loss of precision) and somewhat beyond:

var x = 9001;
var bits = 1;
var limite = 2;
while ( x >= limite ) {
    bits++;
    limite *= 2;
}

But they both use loops, basically asking: does it fit in 1 bit? does it fit in 2 bits? does it fit in 3 bits? etc. I was curious to know if there is a better way to do this.

Note: I’m only interested in know how many bits are needed, not in actually doing that representation. Even because Javascript does not use int, long, unsigned int, etc - and yes double for everything... (and when you use, does not expose to the programmer)

Answer 1

First, the mathematical aspect:

A positive and integer number n has b bits when 2^b-1 < n < 2^b-1.

This means that as long as my integer does not exceed the value of a given power of 2, the amount of bits needed to express that integer is the basis of that power minus one. Examples:

Decimal   Próxima potência de 2  Bitmap      Bits necessários
511       512  (2^10)            111111111   9
967       1024 (2^11)            1111000111  10

So to calculate how many bits b are required to express a number n, we can use logarithms. So:

b_whole = int(log²(n)) + 1

This formula can be divided into three parts:

• log²(n) means the base 2 logarithm of N, which is the exponent to which 2 is raised to reach N. Javascript does not support logarithm calculations on a basis other than 10, so we need to divide Math.log(n) for Math.log(2).
• Int(x) is the entire part of x. In Javascript, the equivalent function is Math.floor().
• +1 plays the exponent to the next power of 2, to compensate for the last position of its number in binary expression.

A way to express this formula in JavaScript would be:

function numBits(numero)
{
    return Math.floor( Math.log(numero) / Math.log(2) ) + 1;
}

I prepared a Jsfiddle where you can test the performance of each method. Assume methods 1 and 2 as in your original question, and 3 as the one in this answer.

My results for a cycle of 1 to 50,000,000 were:

Método 1: 3244 ms
Método 2: 2103 ms
Método 3:  181 ms
(Browser: Google Chrome Version 36.0.1985.125)

Método 1: 1564 ms
Método 2: 2434 ms
Método 3: 2518 ms
(Browser: Internet Explorer 11)

Sources:

• Number of Bits in a Decimal Integer - Exploring Binary
• How can I specify the base for Math.log() in Javascript? - Stack Overflow
• javascript - Number of bits to represent a number - Stack Overflow