JavaScript: convert a 52-bit integer to 20-bit and 32-bit integers

5

In other languages which can represent 64-bit integers, it is possible to do this very easily...

How to store a 64 bit integer in two 32 bit integers and convert back again

How to store a 64 bit integer in two 32 bit integers in Ruby

// convert 64-bit n to two 32-bit x and y
x = (n & 0xFFFFFFFF00000000) >> 32
y =  n & 0xFFFFFFFF

But JavaScript CAN NOT represent 64-bit integers. It can only represent 52-bit integers without problems.

Now that means that it is not possible to convert a 64-bit integer into two 32 bit integers, because it is not even possible to have a 64-bit integer in the first place.

But still, we have 52 bits remaining. My question is: how can we split this 52-bit integer in JavaScript in two 32-bit integers (20 high bits and 32 low bits)

Can someone suggest bit manipulation code like above to do 20-bit and 32-bit split in JavaScript?

Related: How are 32 bit JavaScript numbers resulting from a bit-wise operation converted back to 64 bit numbers

javascript
bit-manipulation
asked on Stack Overflow Oct 6, 2013 by treecoder • edited May 23, 2017 by Community

3 Answers

11

Before we start

First of all, your link contains a minor inaccuracy in stating that "Any whole number less than 252 [...] will safely fit in a JavaScript number. " While technically correct, it is not a tight bound: it can be verified without too much trouble that javascript numbers can store every positive integer up to 253 (but not 253+1).

Some code

Without further ado, the functions you requested, splitting 52-bit numbers into the bottom 32 bits and the 20 top bits:

function to_int52(hi, lo) {
    /* range checking */
    if ((lo !== lo|0) && (lo !== (lo|0)+4294967296))
        throw new Error ("lo out of range: "+lo);
    if (hi !== hi|0 && hi >= 1048576)
        throw new Error ("hi out of range: "+hi);

    if (lo < 0)
    lo += 4294967296;

    return hi * 4294967296 + lo;
}

function from_int52(i) {
    var lo = i | 0;
    if (lo < 0)
    lo += 4294967296;

    var hi = i - lo;
    hi /= 4294967296;
    if ((hi < 0) || (hi >= 1048576)
        throw new Error ("not an int52: "+i);
    return { lo: lo, hi: hi };
}

Where to split

I would not suggest using these though. Javascript bitwise ops are signed (@dandavis: JS does not have UInt32s), and the sign bit causes headaches when we actually want the positive value. Plus V8 has optimizations for (signed) integers that can be stored in 31 bits. Combining these two facts, you should split at no more than 30 bits, the maximum positive size that will fit in a V8 small integer ("smi").

Here's code to split numbers into 30 low bits and 22 high bits:

function int52_30_get(i) {
    var lo = i & 0x3fffffff;
    var hi = (i - lo) / 0x40000000;
    return { lo: lo, hi: hi };
}

You probably don't want to be creating objects though. These should get inlined (if you're actually bothering with functions at all):

function int52_30_get_lo(i) {
    return i & 0x3fffffff;
}

function int52_30_get_hi(i) {
    return (i - (i & 0x3fffffff)) / 0x40000000;
}

And to create the numbers from the low and high parts:

function int52_30_new_safe(hi, lo) {
    return (hi & 0x3fffff) * 0x40000000 + (lo & 0x3fffffff);
}

If you're really sure hi and lo are in range you can skip the masking:

function int52_30_new(hi, lo) {
    return hi * 0x40000000 + lo;
}

Set the high and low parts individually:

/* set high part of i to hi */
i = (hi & 0x3fffff) * 0x40000000 + (i & 0x3fffffff);

/* set low part of i to lo */
i += (lo & 0x3fffffff) - (i & 0x3fffffff);

If you're sure that hi and lo are in range:

/* set high part of i to hi */
i = hi * 0x40000000 + (i & 0x3fffffff);

/* set low part of i to lo */
i += lo - (i & 0x3fffffff);

(These aren't functions because they modify i.)

For extra fun, a function to pull out arbitrary bitfields:

function int52_30_get_bits(i, lsb, nbits) {
    while (lsb >= 32) {
        i /= 4294967296;
        lsb -= 32;
    }
    return (i / (1<<lsb)) & ((1<<nbits)-1);
}

(nbits must be <= 31. The failure mode when nbits is 32 is interesting, and is due to only the 5 low bits of the rhs operand of << being significant, a flaw the javascript spec shares with the x86 ISA.)

More than 52 bits?

It's perfectly possible to use the sign bit to store 53-bit binary numbers as integers from -253 to 253-1. I haven't done this but it should be easy enough. After that it starts to get a bit hairy, and you'll eventually run into the fact that there aren't enough floats to go round (many are NaNs) before you get to 264. Packing 63 binary digits into a float should be theoretically doable, but is left as an exercise for the reader :)

Other approaches

Another approach is to use typed arrays and create a Float view and an Int view: this lets you manipulate the underlying binary representation of floats directly. But then you have to start worrying about endianness and the like.

All the people who are suggesting string manipulation are just crazy.

answered on Stack Overflow Oct 9, 2013 by hexwab • edited May 23, 2017 by Community
4

Well you can do it numerically like this:

function numeric(n) {
    return { 
        hi: Math.floor(n / 4294967296), 
        lo: (n & 0xFFFFFFFF) >>> 0
    }
}

or the string version could be:

function strings(n) { 
    s = n.toString(16);

    if (s.length > 8) { 

        return { 
            hi: parseInt( s.toString(16).slice(0, s.length - 8), 16),
            lo: parseInt( s.toString(16).slice(s.length - 8), 16)
        }
    } else { 
        return { hi: 0, lo: n } 
    }

}

or maybe ...

function stringPad(n) { 
    s = "00000000000"+n.toString(16);
    return { 
        hi: parseInt( s.toString(16).slice(0, s.length - 8), 16),
        lo: parseInt( s.toString(16).slice(s.length - 8), 16)
    }
}

Now, which is faster. To find out I set up a test bed here: http://jsfiddle.net/SpaceDog/ZTJ2p/ (you could also use your favorite JS profiler).

The results (for 100000 calls):

Function: numeric completed in 146 ms
Function: strings completed in 379 ms
Function: stringPad completed in 459 ms

I would have thought strings were faster, and wondered if it was the parseInt call, but no:

Function: stringPadNoParse completed in 386 ms

Now, this isn't very precise as it depends on a lot of other things (again, a profiler might be better) but it does seem like the numeric version is faster and I've run that a few times to test.

But maybe someone will come and provide another way of doing it.

answered on Stack Overflow Oct 9, 2013 by SpaceDog
0

Typed arrays can be used to get the two halves of the double value

var buf = new ArrayBuffer(8);
(new Float64Array(buf))[0] = f;
fl = (new Uint32Array(buf))[0];
fh = (new Uint32Array(buf))[1];

Now you have the mantissa. If needed just extract and shift to get the integer parts

var exp = ((fh >> 20) & 0x7FF) - 1023;
var mant_h = (fh & 0xFFFFF) | (1 << 20);
var mant_l = fl;
if (exp > 52)
    throw new Error ("overflow int53 range");
else if (exp >= 32)
{
    L = mant_h >> (exp - 32);
    H = 0;
}
else if (exp >= 0)
{
    L = (mant_l >> exp) | (mant_h << (32 - exp));
    H = mant_h >> exp;
}

But if you can use a typed array then you should use a 32-bit array with 2 elements for your integers right from the start, no need to deal with double and all the related hassle. That way you have two 32-bit values, not only 20 bits

With the reverse direction you can store a 64-bit int in a JavaScript variable

Note that you can have 64-bit int in Javascript with BigInt64Array and BigUint64Array. You can use it and split into two 32-bit parts instead of double, but it'll be less efficient than a 32-bit array

Since ECMAScript® 2020 there's also a new BigInt type for arbitrary precision integers (with the BigInt object or n suffix). Most major browsers already have support for it

const previousMaxSafe = BigInt(Number.MAX_SAFE_INTEGER);
// ↪ 9007199254740991

const maxPlusOne = previousMaxSafe + 1n;
// ↪ 9007199254740992n

Although it can handle arbitrary-precision integers, one of the rationale for its introduction to the standard is to efficiently work with 64-bit or 128-bit system object handles or IDs, so I suppose it should have very good support for 64-bit integers

answered on Stack Overflow Aug 15, 2018 by phuclv • edited Dec 7, 2019 by phuclv

User contributions licensed under CC BY-SA 3.0