bitwise AND in Javascript with a 64 bit integer_问答_开发者

I am lookin开发者_JS百科g for a way of performing a bitwise AND on a 64 bit integer in JavaScript.

JavaScript will cast all of its double values into signed 32-bit integers to do the bitwise operations (details here).

Javascript represents all numbers as 64-bit double precision IEEE 754 floating point numbers (see the ECMAscript spec, section 8.5.) All positive integers up to 2^53 can be encoded precisely. Larger integers get their least significant bits clipped. This leaves the question of how can you even represent a 64-bit integer in Javascript -- the native number data type clearly can't precisely represent a 64-bit int.

The following illustrates this. Although javascript appears to be able to parse hexadecimal numbers representing 64-bit numbers, the underlying numeric representation does not hold 64 bits. Try the following in your browser:

<html>
  <head>
    <script language="javascript">
      function showPrecisionLimits() {
        document.getElementById("r50").innerHTML = 0x0004000000000001 - 0x0004000000000000;
        document.getElementById("r51").innerHTML = 0x0008000000000001 - 0x0008000000000000;
        document.getElementById("r52").innerHTML = 0x0010000000000001 - 0x0010000000000000;
        document.getElementById("r53").innerHTML = 0x0020000000000001 - 0x0020000000000000;
        document.getElementById("r54").innerHTML = 0x0040000000000001 - 0x0040000000000000;
      }
    </script>
  </head>
  <body onload="showPrecisionLimits()">
    <p>(2^50+1) - (2^50) = <span id="r50"></span></p>
    <p>(2^51+1) - (2^51) = <span id="r51"></span></p>
    <p>(2^52+1) - (2^52) = <span id="r52"></span></p>
    <p>(2^53+1) - (2^53) = <span id="r53"></span></p>
    <p>(2^54+1) - (2^54) = <span id="r54"></span></p>
  </body>
</html>

In Firefox, Chrome and IE I'm getting the following. If numbers were stored in their full 64-bit glory, the result should have been 1 for all the substractions. Instead, you can see how the difference between 2^53+1 and 2^53 is lost.

(2^50+1) - (2^50) = 1
(2^51+1) - (2^51) = 1
(2^52+1) - (2^52) = 1
(2^53+1) - (2^53) = 0
(2^54+1) - (2^54) = 0

So what can you do?

If you choose to represent a 64-bit integer as two 32-bit numbers, then applying a bitwise AND is as simple as applying 2 bitwise AND's, to the low and high 32-bit 'words'.

For example:

var a = [ 0x0000ffff, 0xffff0000 ];
var b = [ 0x00ffff00, 0x00ffff00 ];
var c = [ a[0] & b[0], a[1] & b[1] ];

document.body.innerHTML = c[0].toString(16) + ":" + c[1].toString(16);

gets you:

ff00:ff0000

Here is code for AND int64 numbers, you can replace AND with other bitwise operation

function and(v1, v2) {
    var hi = 0x80000000;
    var low = 0x7fffffff;
    var hi1 = ~~(v1 / hi);
    var hi2 = ~~(v2 / hi);
    var low1 = v1 & low;
    var low2 = v2 & low;
    var h = hi1 & hi2;
    var l = low1 & low2;
    return h*hi + l;
}

This can now be done with the new BigInt built-in numeric type. BigInt is currently (July 2019) only available in certain browsers, see the following link for details:

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt

I have tested bitwise operations using BigInts in Chrome 67 and can confirm that they work as expected with up to 64 bit values.

Javascript doesn't support 64 bit integers out of the box. This is what I ended up doing:

Found long.js, a self contained Long implementation on github.
Convert the string value representing the 64 bit number to a Long.
Extract the high and low 32 bit values
Do a 32 bit bitwise and between the high and low bits, separately
Initialise a new 64 bit Long from the low and high bit
If the number is > 0 then there is correlation between the two numbers

Note: for the code example below to work you need to load long.js.

// Handy to output leading zeros to make it easier to compare the bits when outputting to the console
function zeroPad(num, places){
    var zero = places - num.length + 1;
  return Array(+(zero > 0 && zero)).join('0') + num;
}

// 2^3 = 8
var val1 = Long.fromString('8', 10);
var val1High = val1.getHighBitsUnsigned();
var val1Low = val1.getLowBitsUnsigned();

// 2^61 = 2305843009213693960
var val2 = Long.fromString('2305843009213693960', 10);
var val2High = val2.getHighBitsUnsigned();
var val2Low = val2.getLowBitsUnsigned();

console.log('2^3 & (2^3 + 2^63)')
console.log(zeroPad(val1.toString(2), 64));
console.log(zeroPad(val2.toString(2), 64));

var bitwiseAndResult = Long.fromBits(val1Low & val2Low, val1High & val2High, true);

console.log(bitwiseAndResult);
console.log(zeroPad(bitwiseAndResult.toString(2), 64));
console.log('Correlation betwen val1 and val2 ?');
console.log(bitwiseAndResult > 0);

Console output:

2^3

0000000000000000000000000000000000000000000000000000000000001000

2^3 + 2^63

0010000000000000000000000000000000000000000000000000000000001000

2^3 & (2^3 + 2^63)

0000000000000000000000000000000000000000000000000000000000001000

Correlation between val1 and val2?

true

The Closure library has goog.math.Long with a bitwise add() method.

Unfortunately, the accepted answer (and others) appears not to have been adequately tested. Confronted by this problem recently, I initially tried to split my 64-bit numbers into two 32-bit numbers as suggested, but there's another little wrinkle.

Open your JavaScript console and enter:

0x80000001

When you press Enter, you'll obtain 2147483649, the decimal equivalent. Next try:

0x80000001 & 0x80000003

This gives you -2147483647, not quite what you expected. It's clear that in performing the bitwise AND, the numbers are treated as signed 32-bit integers. And the result is wrong. Even if you negate it.

My solution was to apply ~~ to the 32-bit numbers after they were split off, check for a negative sign, and then deal with this appropriately.

This is clumsy. There may be a more elegant 'fix', but I can't see it on quick examination. There's a certain irony that something that can be accomplished by a couple of lines of assembly should require so much more labour in JavaScript.