побитовое И в Javascript с 64-битным целым числом

Я ищу способ выполнить побитовое И для 64-битного целого числа в JavaScript.

JavaScript преобразует все свои значения типа double в 32-разрядные целые числа со знаком для выполнения побитовых операций (подробности здесь).


javascript integer 64-bit bit-manipulation
person Toby Hede    schedule 06.06.2010    source источник
comment
Перехват stackoverflow.com/q/3637702/632951   -  person Pacerier    schedule 07.08.2017

Ответы (5)


arrow_upward
37
arrow_downward

Javascript представляет все числа как 64-битные числа с плавающей запятой двойной точности IEEE 754 (см. спецификацию ECMAscript, раздел 8.5. ) Все натуральные числа до 2 ^ 53 можно точно закодировать. Младшие биты больших целых чисел обрезаются. Это оставляет вопрос о том, как вы можете даже представить 64-битное целое число в Javascript - исходный числовой тип данных явно не может точно представлять 64-битное целое число.

Следующее иллюстрирует это. Хотя javascript кажется способным анализировать шестнадцатеричные числа, представляющие 64-битные числа, базовое числовое представление не содержит 64 бита. Попробуйте в своем браузере сделать следующее:

<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>

В Firefox, Chrome и IE я получаю следующее. Если бы числа были сохранены в их полном 64-битном великолепии, результат должен был бы быть 1 для всех вычитаний. Вместо этого вы можете увидеть, как теряется разница между 2 ^ 53 + 1 и 2 ^ 53.

(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

Так что ты можешь сделать?

Если вы решите представить 64-битное целое число как два 32-битных числа, то применить побитовое И так же просто, как применить 2 побитовых И к младшему и старшему 32-битным «словам».

Например:

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);

получает вас:

ff00:ff0000
person Oren Trutner    schedule 06.06.2010
comment
Спасибо. В этом случае я на самом деле читаю двоичную строку, содержащую 64-битное значение. Так что я мог каким-то образом превратить это в два 32-битных числа и использовать собственное внутреннее представление для управления этими данными. - person Toby Hede; 07.06.2010
comment
Привет, Тоби! что вы подразумеваете под двоичной строкой? Если это последовательность символов, каждый из которых является символьным эквивалентом 8-битного байта, вы можете сделать: 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)]; Просто следите за порядком байтов. - person Oren Trutner; 07.06.2010
comment
@ Орент Трутнер: будьте осторожны: с Unicode код символа может превышать 255. Я думаю, что ваш код не работает, как только один из байтов имеет высокий бит. - person nalply; 28.08.2011
comment
Действительно. На сегодняшний день мне все еще не ясно, как изначально были представлены 64-битные числа OP. двоичная строка, как в первом комментарии, может означать 8-битные символы, 16-битные символы или даже строку из 64 символов 0 и 1. - person Oren Trutner; 28.08.2011
comment
Вот дополнительная информация, если вы используете javascript с WinRT: msdn.microsoft.com/en-us/library/hh710232 (v = vs.94) .aspx Среда выполнения Windows Int64 - это 64-разрядное целое число со знаком, представленное как стандартное число, если оно попадает в диапазон [-2 ^ 53, 2 ^ 53]. - person Evert; 25.09.2012
comment
Вы также можете использовать класс Closure goog.math.Long. См. Метод and (): docs.closure-library.googlecode.com/git / - person Jeremy Condit; 15.03.2013
comment
Это не отвечает на вопрос. Он говорит мне, что то, что я хочу делать, невозможно, но я уверен, что это так. - person ygoe; 11.06.2018

arrow_upward
14
arrow_downward

Вот код для чисел AND int64, вы можете заменить AND другой побитовой операцией

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;
}
person Andrey    schedule 27.04.2017
comment
Обратите внимание, что для использования другой побитовой операции вы должны заменить & в выражениях для h и l. - person malthe; 04.12.2018
comment
Это здорово, а как насчет сдвига влево / вправо ‹< и ››? - person vanowm; 16.11.2020
comment
@vanowm Пример: 10 ‹< 3 может писать 10 * (2 ** 3), а 10 ›› 3 может писать Math.floor (10 / (2 ** 3)) - person ThangLe; 02.01.2021

arrow_upward
8
arrow_downward

Теперь это можно сделать с помощью нового встроенного числового типа BigInt. В настоящее время BigInt (июль 2019 г.) доступен только в определенных браузерах, подробности см. По следующей ссылке:

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

Я протестировал побитовые операции с использованием BigInts в Chrome 67 и могу подтвердить, что они работают должным образом с 64-битными значениями.

person Gav G    schedule 05.07.2019

arrow_upward
6
arrow_downward

Javascript не поддерживает 64-битные целые числа из коробки. Вот что я в итоге сделал:

  1. Нашел long.js, автономную реализацию Long на github.
  2. Преобразуйте строковое значение, представляющее 64-битное число, в Long.
  3. Извлечь старшие и младшие 32-битные значения
  4. Выполните 32-битное побитовое и между старшими и младшими битами, отдельно
  5. Инициализировать новый 64-битный Long из младшего и старшего бита
  6. Если число> 0, то между двумя числами существует корреляция.

Примечание: для работы приведенного ниже примера кода необходимо загрузить 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);

Вывод в консоль:

2^3

0000000000000000000000000000000000000000000000000000000000001000

2^3 + 2^63

0010000000000000000000000000000000000000000000000000000000001000

2 ^ 3 и (2 ^ 3 + 2 ^ 63)

0000000000000000000000000000000000000000000000000000000000001000

Корреляция между val1 и val2?

правда

person bounav    schedule 20.10.2016

arrow_upward
4
arrow_downward

В библиотеке Closure есть goog.math.Long с поразрядным add() методом. .

person Janus Troelsen    schedule 09.07.2013