Najszybszy sposób konwersji liczb całkowitych na dowolnie uporządkowane tablice bajtów w JavaScript?

Question

Zamierzam przekonwertować zakres MIN_SAFE_INTEGER do MAX_SAFE_INTEGER zakresu kodu JavaScript (53-bitów bez znaku) na ciąg bitów rozłożonych na 7 bajtów przesuniętych o dwa, aby umożliwić identyfikatory znaków i puste.

dotąd najlepszy mam wymyślić to:

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

Jak można powiedzieć tuż, to byłoby okropnie wolno (a bity wciąż nie zostały przesunięte dwa miejsca na wszystkie 7 aktywnych bajtów.)

Czy jest jakiś sposób, aby to zrobić szybciej? Idealnie unikając parsowania napisów w ogóle?

Answer 1

Uderzyłem w książki, a także kilku innych znajomych z mojej strony z matematyki, a naszym obecnym werdyktem jest to, że nie można tego zrobić tak, jak to opisujesz.

Myślę, że utknąłeś z analizą łańcuchów.

Answer 2

Bitowe ops w javascript mają szerokość tylko 32 bity. Ale przesuwanie jest równoznaczne z mnożeniem lub dzieleniem przez potęgę dwóch, a dzieje się to z pełną precyzją zmiennoprzecinkową.

To, co chcesz zrobić, jest proste. Przenieś, aby uzyskać interesującą część w bitach niższego rzędu, i zamasuj resztę. E.g. masz dużą liczbę 0x123456789abc (20015998343868).

0x123456789abc/0x1 = 0x123456789abc. Bitowe ORAZ z 0xff daje 0xbc.

0x123456789abc/0x100 = 0x123456789a.bc. Bitowe ORAZ z 0xff daje 0x9a.

0x123456789abc/0x10000 = 0x12345678.9abc. Bitowe ORAZ z 0xff daje 0x78.

I tak dalej. Kod:

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

Z życia Uint8Array jest jeszcze prostsze: maskowanie z 0xFF jest niejawna jak Uint8Arrays mogą przechowywać tylko liczby całkowite od 0 do 255. Ale ja zostawiłem go w jasności, i tak, że wynik będzie to samo z różnymi typami tablic.

Ten kod tworzy tablicę typu little-endian, np. toUint8Array(0x123456789abc) zwraca [0xbc,0x9a,0x78,0x56,0x34,0x12,0]. Jeśli chcesz big-endian, czyli bajty w odwrotnej kolejności, zamień arr[i] na arr[6-i].

(Jeśli chcesz, bity w każdym wpisie tablicy w odwrotnej kolejności jest to nieco bardziej skomplikowane Wymień (d/j) & 0xff z bitrev((d/j) & 0xff), gdzie bitrev wyglądać tak:.

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

)

Na koniec działa to wyłącznie na dodatnich liczbach całkowitych. Ale twoja idea "przesuwania na dwójkę" jest łatwo zaimplementowana. d*4 jest przesunięty w lewo o dwa bity.I d < 0 ? -d : d (lub Math.abs(d)) jest bezwzględną wartością d. Tak więc arr = toUint8Array((d<0) ? 1-d*4 : d*4) zwraca d przesunięte w lewo o dwa bity, z bitem znaku w najmniej znaczącym bicie (LSB).

I można sprawdzić za brak numerów z isFinite(), ale trzeba uważać, aby nazwać tylko na liczbach, jak isFinite(null), powiedzmy, jest rzeczywiście true powodu ukrytych reguł odlewniczych (ta jest ustalona w 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); 
}