¿Cuál es la manera más rápida de hacer un desplazamiento de bits circular recto en una matriz de bytes

Question

Si tengo la matriz:

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

El resultado de un cambio de 1 bit es:

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

El tamaño de la matriz no es fijo, y el cambio será de 1 a 7 inclusive. Actualmente tengo el siguiente código (que funciona bien):

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

¿Hay una forma más rápida de lograr esto que mi enfoque actual?

Answer 1

La única forma de averiguarlo es con el evaluación comparativa exhaustiva, y las implementaciones más rápidas varían de una plataforma a otra. Use una herramienta como Caliper si realmente necesita optimizar esto.

Answer 2

Puede generalizar esto a los largos y más de un desplazamiento de bits si se quiere

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

asumiendo rotr se define.

Answer 3

Una de las cosas que puede hacer es reemplazar (byte[a]&0xff)>>b con byte[a]>>>b

Además, no es necesario &0xff cuando lo que queda es cambiante.

Aunque no importe, agregar final a tmp o mover la declaración fuera del ciclo puede ayudar un poco.

Otra cosa que podría intentar es:

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

Entonces resolver bytes [bytes.length-1] después.

Ese reverso para el lazo también puede ayudar si eres supersticioso. Lo he visto funcionar antes.

Análisis del bucle por pasada:

la suya: 3 tareas, dos turnos, uno o, uno del elenco.

mina: 2 asignaciones, dos turnos, uno o uno elenco.

Answer 4

Uso ByteBuffer.wrap para obtener un búfer que envuelve su byte[] y luego usar ByteBuffer.asLongBuffer() para obtener una vista que le permite extraer y manipular long s según lo sugerido por @NiklasB. aprovechando así la capacidad del hardware para desplazar grandes trozos de bits.