Самый быстрый способ преобразования целого числа в произвольно упорядоченные массивы байтов в JavaScript?

Я хочу преобразовать диапазон MIN_SAFE_INTEGER через MAX_SAFE_INTEGER номера JavaScript (53-биты, не включая знак), в строку бит, разбросанную по 7 байтам, сдвинутую на два, чтобы разрешить знак и нулевые идентификаторы.

До сих пор лучшее, что я придумал, это:

function toUint8Array(data) {
    data = data.toString(2);
    data = new Array(65 - data.length).join('0') + data;
    var ret = new Uint8Array(data.length / 8);
    for (var i = 0; i < 8; i++) {
        ret[i] = 0;
        ret[i] += (data[i * 8] == '1' ? 128 : 0);
        ret[i] += (data[(i * 8) + 1] == '1' ? 64 : 0);
        ret[i] += (data[(i * 8) + 2] == '1' ? 32 : 0);
        ret[i] += (data[(i * 8) + 3] == '1' ? 16 : 0);
        ret[i] += (data[(i * 8) + 4] == '1' ? 8 : 0);
        ret[i] += (data[(i * 8) + 5] == '1' ? 4 : 0);
        ret[i] += (data[(i * 8) + 6] == '1' ? 2 : 0);
        ret[i] += (data[(i * 8) + 7] == '1' ? 1 : 0);
    }
    return (ret);
}

Fiddle

Как вы сразу можете сказать, это было бы отвратительно медленным (и биты все еще не были сдвинуты на два места по всем 7 активным байтам.)

Есть ли способ сделать это быстрее? В идеале, избегая синтаксического анализа вообще?

Ответы

Ответ 1

Побитовые операторы в javascript имеют ширину всего 32 бита. Но смещение эквивалентно умножению или делению на мощность в два, и это происходит с полной точностью с плавающей точкой.

Итак, что вы хотите сделать, просто. Сдвиньте, чтобы получить интересную часть в младших битах и ​​замаскируйте остальные. Например. у вас есть большое число 0x123456789abc (20015998343868).

0x123456789abc/0x1 = 0x123456789abc. Побитовое И с 0xff дает 0xbc.

0x123456789abc/0x100 = 0x123456789a.bc. Побитовое И с 0xff дает 0x9a.

0x123456789abc/0x10000 = 0x12345678.9abc. Побитовое И с 0xff дает 0x78.

И так далее. Код:

function toUint8Array(d) {
    var arr = new Uint8Array(7);
    for (var i=0, j=1; i<7; i++, j *= 0x100) {
        arr[i] = (d / j) & 0xff;
    }
    return arr;
}

С жизнью Uint8Array еще проще: маскирование с помощью 0xff неявно, так как Uint8Arrays может хранить только целые числа от 0 до 255. Но я оставил его для ясности и так, чтобы результат был таким же с разными типами массивов.

Этот код создает малоинтенсивный массив, например. toUint8Array(0x123456789abc) возвращает [0xbc,0x9a,0x78,0x56,0x34,0x12,0]. Если вы хотите использовать big-endian, т.е. Байты в обратном порядке, замените arr[i] на arr[6-i].

(Если вы хотите, чтобы бит в каждой записи массива находился в противоположном порядке, это немного сложнее. Замените (d / j) & 0xff на bitrev((d / j) & 0xff), где bitrev выглядит примерно так:

function bitrev(byte) {
   var table = [ 0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110,
                 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111 ];
   return table[byte >> 4] + (table[byte & 0xf] << 4);
}

)

Наконец, это работает только на положительные целые числа. Но ваша идея "сдвинуть-на-два" легко реализуется. d*4 d сдвинут влево на два бита. И d < 0 ? -d : d (или Math.abs(d)) является абсолютным значением d. Таким образом, arr = toUint8Array((d<0) ? 1-d*4 : d*4) возвращает d, сдвинутое влево на два бита со знаковым битом в младшем значении (LSB).

И вы можете проверить не-номера с помощью isFinite(), но вы должны быть осторожны, чтобы вызывать его только по номерам, поскольку isFinite(null), скажем, на самом деле true из-за неявных правил литья (это исправлено в ES6):

function toUint8Array_shifted_signed(d) {
   /* bit 0 is sign bit (0 for +ve); bit 1 is "not-a-number" */
   if (typeof d !== 'number' || !isFinite(d)) {
       d = 2; 
   } else {
       d = (d<0) ? 1-d*4 : d*4;
   }

   return toUint8Array(d);
}

Ответ 2

Я попал в книги и еще несколько друзей моей команды по математике, и наш нынешний вердикт заключается в том, что это невозможно сделать, поскольку вы описываете его.

Я думаю, что вы застряли в синтаксическом разборе строк.