Using bitwise operators with large numbers in javascript [duplicate]

Question

I am writing a Javascript version of this Microsoft string decoding algorithm and its failing on large numbers. This seems to be because of sizing (int / long) issues. If I step through the code in C# I see that the JS implementation fails on this line

n |= (b & 31) << k;

This happens when the values are (and the C# result is 240518168576)

(39 & 31) << 35

If I play around with these values in C# I can replicate the JS issue if b is an int. And If I set b to be long it works correctly.

So then I checked the max size of a JS number, and compared it to the C# long result

240518168576 < Number.MAX_SAFE_INTEGER = true

So.. I can see that there is some kind of number size issue happening but do not know how to force JS to treat this number as a long.

Full JS code:

private getPointsFromEncodedString(encodedLine: string): number[][] {

    const EncodingString = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-";

    var points: number[][] = [];

    if (!encodedLine) {
        return points;
    }

    var index = 0;
    var xsum = 0;
    var ysum = 0;

    while (index < encodedLine.length) {
        var n = 0;
        var k = 0;

        debugger;

        while (true) {
            if (index >= encodedLine.length) {
                return points;
            }

            var b = EncodingString.indexOf(encodedLine[index++]);

            if (b == -1) {
                return points;
            }

            n |= (b & 31) << k;
            k += 5;
            if (b < 32) {
                break;
            }
        }

        var diagonal = ((Math.sqrt(8 * n + 5) - 1) / 2);

        n -= diagonal * (diagonal + 1) / 2;

        var ny = n;
        var nx = diagonal - ny;

        nx = (nx >> 1) ^ -(nx & 1);
        ny = (ny >> 1) ^ -(ny & 1);

        xsum += nx;
        ysum += ny;

        points.push([ysum * 0.000001, xsum * 0.000001]);
    }

    console.log(points);

    return points;
}

Expected input output:

Encoded string

qkoo7v4q-lmB0471BiuuNmo30B

Decoded points:

35.89431, -110.72522
35.89393, -110.72578
35.89374, -110.72606
35.89337, -110.72662

Can you click [<>] and produce a minimal reproducible example with example input and expected output? — mplungjan
– mplungjan, Commented Jun 21, 2019 at 11:06
BigInts will help you console.log((1n << 32n).toString()), but the support is not quite there .. — Jonas Wilms
– Jonas Wilms, Commented Jun 21, 2019 at 11:21
While the duplicate explains what's happening, it doesn't really help with resolving the issue. — Luaan
– Luaan, Commented Jun 21, 2019 at 12:07
I've fixed your code to work with vanilla Javascript (well, Typescript :) - jsfiddle.net/Luaan/jrkpgu8d/3 Should be pretty straight forward, ask away if there's anything unclear. — Luaan
– Luaan, Commented Jun 24, 2019 at 10:50
Yeah, I think there's definitely some subtle difference with your C# implementation of the encoding - the Javascript version at learn.microsoft.com/en-us/bingmaps/rest-services/elevations/… gives me the expected vx1vilihnM6hR7mEl2Q as result. I think you need to be more careful with where you use integers - in the Javascript version, integers are only used for the bitwise operations, everything else is double. Order of operations (namely * vs. /) might also matter, especially on integers. — Luaan
– Luaan, Commented Jun 24, 2019 at 15:59

ponury-kostek · Accepted Answer · 2019-06-21 12:59:23Z

10

Bitwise operators treat their operands as a sequence of 32 bits (zeroes and ones), rather than as decimal, hexadecimal, or octal numbers. For example, the decimal number nine has a binary representation of 1001. Bitwise operators perform their operations on such binary representations, but they return standard JavaScript numerical values.

(39 & 31) << 35 tries to shift 35 bits when there only 32

Bitwise Operators

To solve this problem you could use BigInt to perform those operations and then downcast it back to Number

Number((39n & 31n) << 35n)

You can try this:

function getPointsFromEncodedString(encodedLine) {

    const EncodingString = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-";

    var points = [];

    if (!encodedLine) {
        return points;
    }

    var index = 0;
    var xsum = 0;
    var ysum = 0;

    while (index < encodedLine.length) {
        var n = 0n;
        var k = 0n;


        while (true) {
            if (index >= encodedLine.length) {
                return points;
            }

            var b = EncodingString.indexOf(encodedLine[index++]);

            if (b === -1) {
                return points;
            }

            n |= (b & 31n) << k;
            k += 5n;
            if (b < 32n) {
                break;
            }
        }

        var diagonal = ((Math.sqrt(8 * Number(n) + 5) - 1) / 2);

        n -= diagonal * (diagonal + 1) / 2;

        var ny = n;
        var nx = diagonal - ny;

        nx = (nx >> 1) ^ -(nx & 1);
        ny = (ny >> 1) ^ -(ny & 1);

        xsum += Number(nx);
        ysum += Number(ny);

        points.push([ysum * 0.000001, xsum * 0.000001]);
    }

    console.log(points);

    return points;
}

edited Jun 21, 2019 at 12:59

answered Jun 21, 2019 at 11:07

ponury-kostek

8,0835 gold badges27 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Chris Over a year ago

Hey, thanks for this, is there anyway around it?

ponury-kostek Over a year ago

@Chris you can use BigInt Number((39n & 31n) << 35n)

Chris Over a year ago

Thank you, unfortunately I believe BigInt doesn't work in Edge / IE11 so may have to look at BigInteger instead

Luaan Over a year ago

@Chris I do have a solution that uses Javascript numbers, but I can't post it, since the question is closed :P

ponury-kostek Over a year ago

@Luaan I voted for reopen

|

Collectives™ on Stack Overflow

Using bitwise operators with large numbers in javascript [duplicate]

1 Answer 1

6 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Linked

Related