Il modo più veloce per convertire un intero in array di byte arbitrariamente ordinati in JavaScript?

Question

Sto cercando di convertire l'intervallo MIN_SAFE_INTEGER tramite MAX_SAFE_INTEGER di un numero JavaScript (53 bit che non include il segno) in una stringa di bit distribuiti su 7 byte spostati due per consentire identificatori di segno e nulli.

Così lunga il migliore che è venuta in mente è:

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

Come si può dire a destra fuori, questo sarebbe abominevole lento (e il bit ancora non sono stati spostati due posti su tutti i 7 byte attivi)

C'è un modo per farlo più veloce? Idealmente evitando l'analisi delle stringhe del tutto?

Answer 1

Mi sono imbattuto nei libri e un paio di amici CS della mia squadra di matematica, e il nostro attuale verdetto è che questo non può essere fatto mentre lo descrivi.

Penso che tu sia bloccato con l'analisi delle stringhe.

Answer 2

Le operazioni bit a bit in javascript hanno solo 32 bit di larghezza. Ma lo spostamento è equivalente alla moltiplicazione o alla divisione per una potenza di due, e questi avvengono con la massima precisione a virgola mobile.

Quindi quello che vuoi fare è semplice. Sposta per ottenere la parte interessante nei bit di basso ordine e maschera il resto. E.g. hai un grande numero 0x123456789abc (20015998343868).

0x123456789abc/0x1 = 0x123456789abc. Bitwise AND con 0xff fornisce 0xbc.

0x123456789abc/0x100 = 0x123456789a.bc. Bitwise AND con 0xff fornisce 0x9a.

0x123456789abc/0x10000 = 0x12345678.9abc. Bitwise AND con 0xff restituisce 0x78.

E così via. Codice:

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

Con una vita Uint8Array è ancora più facile: il mascheramento con 0xff è implicita come Uint8Arrays possono memorizzare solo numeri interi compresi tra 0 e 255. Ma ho lasciato in per chiarezza, e in modo che il risultato sarà lo stesso con diversi tipi di array.

Questo codice produce un array little-endian, ad es. toUint8Array(0x123456789abc) restituisce [0xbc,0x9a,0x78,0x56,0x34,0x12,0]. Se si desidera big-endian, ovvero i byte nell'ordine opposto, sostituire arr[i] con arr[6-i].

(Se si desidera che i bit in ogni voce array in ordine inverso questo è leggermente più complicato Sostituire (d/j) & 0xff con bitrev((d/j) & 0xff), dove bitrev simile a questa:.

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

)

Infine, funziona solo su numeri interi positivi. Ma la tua idea del passaggio a due è facilmente implementabile. d*4 è spostato a sinistra di due bit.E d < 0 ? -d : d (o Math.abs(d)) è il valore assoluto di d. Quindi arr = toUint8Array((d<0) ? 1-d*4 : d*4) restituisce d spostato a sinistra di due bit, con il bit di segno nel bit meno significativo (LSB).

E si può verificare la presenza di non-numeri con isFinite(), ma bisogna stare attenti a chiamarla solo sui numeri, come isFinite(null), per esempio, è in realtà true a causa di regole di fusione implicite (questo è stato risolto in 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); 
}