Minimum bits needed to represent a natural number

Navigation
5

What is the most performative way of finding the minimum number of bits needed to represent a natural number (i.e., no signal) in JavaScript? Is there 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 greater than this): 

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

And this works up to 2^53 (the largest integer representably guaranteed without loss of precision) and somewhat beyond: 

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

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

Note: I'm only interested in knowing how many bits are needed, not really actually doing that rendering. Even though JavaScript does not use int , long , unsigned int , etc - but double for everything ... (and when using , does not expose to the programmer)

    
asked by anonymous 26.07.2014 / 17:29

1 answer

4

First, the mathematical aspect:

A positive integer and n has b bits when 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 needed to express a number n , we can use logarithms. So:

b integer = int (log 2

This formula can be divided into three parts:

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

One way to express this formula in JavaScript would be: 

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

I have 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:

26.07.2014 / 18:14
How to convert a std :: string into a QString? Extend the PHPWord class in CI - class not found