Длинные целые числа из потоков данных в Javascript

Это было интересно.

Задача: в Javascript считать 8 байтов из массива (например, файла или сетевого пакета) и преобразовать их в число. 53-битная точность в порядке (Javascript хранит числа как 64-битные числа с плавающей запятой с 53-битной мантиссой). Используйте Uint8Array как наше представление массива байтов.

Другие языки имеют 64-битные целые числа, и это просто. В других языках также есть uint, которые упрощают работу с единицами в старшем значащем бите. Однако Javascript обрабатывает все числа как числа с плавающей запятой с 53-битной точностью (оставшиеся 11 бит являются экспонентой). Чтобы обойти это, появилось множество библиотек Big Integer, которые позволяют использовать 64-битные или строковые большие числа произвольной длины. Однако я работаю с кодом, который начал свою жизнь на Java, и до сих пор должен работать на Java, поэтому сильно рефакторить не хочется. Кроме того, 53-битная точность подходит для этой проблемы, потому что эти числа на самом деле являются только временными метками. Я хочу обрабатывать эту математику на уровне абстракции, который дает мне обычный номер Javascript для использования в другом месте.

Классический подход: битовый сдвиг

Подход со сдвигом битов отлично работает в языках с 64-битными целыми числами и выглядит примерно так:

for (var i = 0; i < 8; i++) { 
    if (i > 0) num <<=8; 
    num |= arr[i] & 0xFF; 
} 

Однако сдвиг битов в Javascript превращает числа в 32-битные целые числа (они прекрасно вписываются в 64-битное число с плавающей запятой). Таким образом, этот подход полностью смещает ваши самые значащие четыре байта из числа.

Это не сработает для нас.

Математический подход более высокого уровня: умножить и сложить

Умножение числа на 256 (0x100) и добавление следующего байта является математическим эквивалентом сдвига влево на 8, и мы не потеряем 21 старший бит точности. Более того, поскольку битовый сдвиг не увеличивает производительность в Javascript, использование обычной математики вполне допустимо. Этот подход выглядит следующим образом:

for (var i = 0; i < 8; i++) { 
    if (i > 0) num *= 0x100; 
    num += arr[i] & 0xFF; 
}

Однако это приводит к очень неправильным результатам, когда число отрицательное и дополняется единицами до самого левого края. После достаточного количества прогонов цикла num начинает выглядеть отрицательным, а добавление arr[i] к отрицательному числу сдвигает num в неправильном направлении.

Два 32-битных целочисленных подхода

В конце концов я решил, что безопаснее прочитать 8 байтов в два слова по 4 байта и вычислить правильное 53-битное число. Таким образом, я не собирался терять ни одного бита, пока мне не нужно было выбросить старшие 21 бит.

Подобно подходу «умножить на 256 и сложить», он отлично работает (и легко) для положительных чисел:

for (var i = 0; i < 8; i++) { 
    if (i < 4) { 
        if (i > 0) high = high * 0x100; 
        high += arr[i] & 0xFF; 
    } else { 
        if (i > 4) low = low * 0x100; 
        low += arr[i] & 0xFF; 
    } 
} 
num = high * 0x100000000 + low;

Однако теперь отрицательные значения представляют собой проблему, потому что мы используем только младшие 32 бита 53-битной мантиссы с плавающей запятой, поэтому ни старшее, ни младшее целое слово не выглядят как отрицательные числа до этого шага умножения. (Запомните это, это снова будет важно позже.) Если во время умножения high * 0x100000000 дает нам 1 в бите 53, это внезапно выглядит отрицательным для Javascript, добавляя к нему положительное значение low, что ж, это неправильный ответ.

Мы должны быть умнее.

Математика дополнения до двух

Отрицательные числа представлены в форме дополнения до двух, что, если вы помните свой CS101, дает нам одно дополнительное представление числа, чем просто использование бита знака. Это также делает некоторые элегантные математические вычисления на уровне битов. Но мы работаем на Javascript, поэтому математика на уровне битов уже не элегантна; на самом деле, это продолжает доставлять нам неприятности.

Преобразование числа в дополнение до двух на бумаге просто: поменяйте местами биты и прибавьте единицу. Теперь у вас есть негативное представление вашей ценности. Так что это похоже на то, что это должно работать:

if (high >= 0x80000000) {  // see if 64-bit number is negative 
    high ^= 0xFFFFFFFF; 
    low ^= 0xFFFFFFFF; 
    num = -(high * 0x100000000 + low + 1); 
}

Но вот где Javascript снова становится странным, и все дело в математике на уровне битов, внезапно превращающей числа в 32-битные целые числа со знаком. Запустите консоль или узел и попробуйте следующее:

> var num = 123; 
> num ^= 0xFFFFFFFF; 
-124

Видите это отрицательное число? Если вы перевернете биты в младшем слове и в бите 32 будет 1, число станет отрицательным. high * 0x100000000 + low теперь является вычитанием, а не сложением, и мы получаем неверный ответ. У нас та же проблема, с которой мы столкнулись в прошлый раз, когда мы пробовали эту строку кода, за исключением того, что на этот раз low является отрицательным значением.

Частный случай младшее слово

Таким образом, способ обойти это состоит в том, чтобы убедиться, что когда мы переворачиваем биты младшего слова, у нас никогда не будет отрицательного числа. Кажется, это работает:

if (high >= 0x80000000) { 
    high ^= 0xFFFFFFFF; 
    var lowIsPositive = false; 
    if (low < 0) {
        low ^= 0xFFFFFFFF; 
    } else { 
        lowIsPositive = true; 
        low ^= 0x7FFFFFFF; 
    } 
    num = -(high * 0x100000000 
        + low 
        + 1 
        + (lowIsPositive ? 0x80000000 : 0)); 
} else {
    num = high * 0x100000000 + low;
}

Одно любопытное замечание: последняя строка кода по-прежнему работает, не беспокоясь о знаке low, потому что, когда мы считывали байты в число, мы использовали метод умножения и сложения вместо побитового. сменный подход. Даже если 32-й бит low равен 1, он все равно считается положительным числом. Пока, конечно, мы не проведем побитовую математику и Javascript не превратит ее в 32-битное целое число со знаком.

Мораль

Мои выводы из этого упражнения:

• Иногда понимание представления чисел даже более важно в языках высокого уровня, таких как Javascript, чем в языках низкого уровня, таких как C.
• Смешивание побитовой и числовой математики в Javascript опасно; будь осторожен

Первоначально опубликовано на razorborg.com.