Какой самый быстрый способ сделать правильное круговое смещение битов в массиве байтов

Question

Если у меня есть массив:

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

Результат для сдвига в 1 бит:

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

Размер массива не фиксирован, а смещение будет от 1 до 7 включительно. В настоящее время у меня есть следующий код (который отлично работает):

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

Есть ли более быстрый способ добиться этого, чем мой нынешний подход?

Answer 1

Единственный способ выяснить это с помощью тщательного бенчмаркинга, и самые быстрые реализации будут варьироваться от платформы к платформе.Используйте такой инструмент, как Caliper , если вам действительно нужно оптимизировать это.

Answer 2

Одна из вещей, которую вы можете сделать, это заменить (byte[a]&0xff)>>b на byte[a]>>>b

Кроме того, вам не нужно &0xff, когда вы переключаетесь влево.

Хотя это может и не иметь значения, добавление final к tmp или удаление объявления из цикла может помочь совсем немного.

Другая вещь может попробовать это:

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

Затем вы решаете байты [bytes.length-1].

Этот обратный цикл также может помочь, если вы суеверны. Я видел, как это работает раньше.

Анализ циклов за проход:

ваш: 3 задания, две смены, одна или, одна каста.

мой: 2 задания, две смены, одна или, одна каста.

Answer 3

Используйте ByteBuffer.wrap, чтобы получить буфер, который обернет ваш byte[], а затем используйте ByteBuffer.asLongBuffer(), чтобы получить представление, позволяющее извлекать и манипулировать long s. как предложено @NiklasB. таким образом, используя в своих интересах способность аппаратного обеспечения сдвигать большие куски битов.

Answer 4

Вы можете обобщить это на длинные и более чем один битовый сдвиг, если вам нравится

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

при условии, что rotr определено.