Qual è il modo più veloce per fare uno spostamento a destra circolare bit su un array di byte

Question

Se ho la matrice:

{01101111,11110000,00001111} // {111, 240, 15} 

Il risultato per un turno di 1 bit è:

{10110111,11111000,00000111} // {183, 248, 7} 

La dimensione dell'array non è fisso e lo spostamento sarà compreso tra 1 e 7 inclusi. Attualmente ho il seguente codice (che funziona bene):

private static void shiftBitsRight(byte[] bytes, final int rightShifts) { 
    assert rightShifts >= 1 && rightShifts <= 7; 

    final int leftShifts = 8 - rightShifts; 

    byte previousByte = bytes[0]; // keep the byte before modification 
    bytes[0] = (byte) (((bytes[0] & 0xff) >> rightShifts) | ((bytes[bytes.length - 1] & 0xff) << leftShifts)); 
    for (int i = 1; i < bytes.length; i++) { 
     byte tmp = bytes[i]; 
     bytes[i] = (byte) (((bytes[i] & 0xff) >> rightShifts) | ((previousByte & 0xff) << leftShifts)); 
     previousByte = tmp; 
    } 
} 

Esiste un modo più rapido per raggiungere questo rispetto al mio attuale approccio?

Answer 1

L'unico modo per scoprirlo è con approfondita benchmarking, e più veloci implementazioni variano da piattaforma per platfrm. Usa uno strumento come Caliper se hai davvero bisogno di ottimizzare questo.

Answer 2

È possibile generalizzare questo a anela e più di un turno po 'se vi piace

// for a 1-bit rightshift: 
// first rotate each byte right by one 
for (i = 0; i < n; i++) b[i] = rotr(b[i], 1); 
// get rightmost bit 
bit = b[n-1] & 0x80; 
// copy high order bit from adjacent byte 
for (i = n; --i >= 1;){ 
    b[i] &= 0x7f; 
    b[i] |= (b[i-1] & 0x80); 
} 
// put in the rightmost bit on the left 
b[0] = (b[0] & 0x7f) | bit; 

assumendo rotr è definito.

Answer 3

Una delle cose che puoi fare è sostituire (byte[a]&0xff)>>b con byte[a]>>>b

Inoltre, non è necessario &0xff quando si sono lasciati spostamento.

Anche se potrebbe non essere importante, aggiungere la finale a tmp o spostare la dichiarazione fuori dal ciclo può aiutare un po '.

Un'altra cosa potrebbe provare è:

int tmp=bytes[bytes.length-1]; 
for (int i = bytes.length-2; i >=0; i--) { 
    tmp=(tmp<<8)|bytes[i]; 
    bytes[i] = (byte) (tmp>>>rightShifts); 
} 

Poi si risolve byte [bytes.length-1] in seguito.

L'inversione del ciclo può anche aiutare se sei superstizioso. L'ho visto funzionare prima. Analisi Loop

per passata:

vostro: 3 assegnazioni, due turni, uno o, uno del cast.

miniera: 2 assegnazioni, due turni, uno o un cast.

Answer 4

Usa ByteBuffer.wrap per ottenere un buffer che avvolge il tuo byte[] e quindi utilizzare ByteBuffer.asLongBuffer() per ottenere una vista che permette di estrarre e manipolare long s come suggerito da @NiklasB. approfittando così della capacità dell'hardware di spostare pezzi più grandi di bit.