Number of bits to represent a number

Question

I'm trying to write a function to return the number of bits a positive integer less that the Javascript limit of (2^53)-1 is. However im being hit by precision problems, and want to avoid big integer libraries.

Method 1:

function bitSize(num)
{
return Math.floor( Math.log(num) / Math.log(2) ) + 1;
}

Pass: bitSize( Math.pow(2, 16) -1 ) = 16
Pass: bitSize( Math.pow(2, 16) ) = 17
Fail (Should be 48): bitSize( Math.pow(2, 48) -1 ) = 49 
Pass: bitSize( Math.pow(2, 48) ) = 49

Method 2:

function bitSize(num)
{
var count = 0;
while(num > 0)
{
    num = num >> 1;
    count++;
}
return count;
}

Pass: bitSize( Math.pow(2, 16) -1 ) = 16
Pass: bitSize( Math.pow(2, 16) ) = 17
Fail (Should be 48): bitSize( Math.pow(2, 48) -1 ) = 1
Fail (Should be 49): bitSize( Math.pow(2, 48) ) = 1

Both methods fail to precision issues I think.

Can anyone suggest an alternative method that will work for numbers between 0 -> 2^53-1

Thanks.

Answer 1

You can do:

function bitSize(num) {
    return num.toString(2).length;
}

The toString() method of Number takes the radix as an optional argument.

Here are some tests. Works on Chrome, Safari, Opera, and Firefox. No access to IE, sorry.

Answer 2

Bitwise operations will only work reliably in Javascript for "integers" up to 32-bits. To quote from The Complete JavaScript Number Reference:

Bitwise operations are a bit of a hack in Javascript. Since all numbers in Javascript are floating point, and bitwise operators only work on integers, Javascript does a little behind the scenes magic to make it appear bitwise operations are being applied to a 32bit signed integer.

Specifically, Javascript takes the number you are working on and takes the integer portion of the number. It then converts the integer to the most number of bits that number represents, up to 31 bits (1 bit for the sign). So 0 would create a two bit number (1 for the sign, and 1 bit for 0), likewise 1 would create two bits. 2 would create a 3 bit number, 4 would create a 4 bit number, etc…

It's important to realize that you're not guaranteed a 32bit number, for instance running not on zero should, in theory, convert 0 to 4,294,967,295, instead it will return -1 for two reasons, the first being that all numbers are signed in Javascript so "not" always reverses the sign, and second Javascript couldn't make more than one bit from the number zero and not zero becomes one. Therefore ~0=-1.

So bitwise signs in Javascript are up to 32 bits.

As Anurag notes, you should simply use the built-in num.toString(2) in this situation instead, which outputs a minimal length string of ASCII '1's and '0's, which you can simply take the length of.