I am looking 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).
bitwise AND in Javascript with a 64 bit integer
Asked Answered
Hooking https://mcmap.net/q/75984/-how-to-do-bitwise-and-in-javascript-on-variables-that-are-longer-than-32-bit/632951 –
Femur
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
Thanks. In this case I am actually reading in a binary string containing a 64-bit value. So I could somehow turn that into two 32 bit numbers and use my own internal representation to manage that data. –
Hausa
Hey Toby; what do you mean by binary string? If this is a sequence of characters, each of which is the character equivalent of an 8-bit byte, you could do: var a = [ s.charCodeAt(0) + (s.charCodeAt(1) << 8) + (s.charCodeAt(2) << 16) + (s.charCodeAt(3) << 24), s.charCodeAt(4) + (s.charCodeAt(5) << 8) + (s.charCodeAt(6) << 16) + (s.charCodeAt(7) << 24) ]; Just keep an eye on the endian-ness of things. –
Spleeny
@Orent Trutner: be careful here: with Unicode, a char code could exceed 255. I think that your code fails as soon as one of the bytes has the high bit set. –
Birl
Indeed. To-date, I am still not clear on how the OP's 64-bit numbers were originally represented. "a binary string", as in the first comment, could mean 8-bit characters, 16-bit characters, or even a string of 64 "0" and "1" characters. –
Spleeny
Here is some more info if you use javascript with WinRT: msdn.microsoft.com/en-us/library/hh710232(v=vs.94).aspx A Windows Runtime Int64 is a signed 64-bit integer, represented as a standard number if it falls within the range [-2^53, 2^53]. –
Bernicebernie
You can also use Closure's goog.math.Long class. See the and() method: docs.closure-library.googlecode.com/git/… –
Putupon
This doesn't answer the question. It tells me that what I want to do is not possible, but I'm sure it is. –
Madden
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;
}
Note that to use another bitwise operation you would replace
& in the expressions for h and l. –
Sarita This is great, what about left/right shift << and >> ? –
Bahadur
@Bahadur Example: 10 << 3 can write 10 * (2 ** 3), and 10 >> 3 can write Math.floor(10 / (2 ** 3)) –
Schilling
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
Longfrom 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.
© 2022 - 2024 — McMap. All rights reserved.