什么是对字节数组进行右位移/循环移位的最快方法？

Question

如果我有一个数组：

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

一个二进制位移的结果是：

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

数组大小不固定，移位范围为1至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;
   }
}

有比我的当前方法更快的实现方式吗？

- mota

---

我认为首先将数据分组成“长块”对提高性能会有帮助。 - Niklas B.

如果这是用于图形方面的，另一个值得考虑的选项是使用一种运行长度编码格式。那么移位就不必更改线路中间的所有运行长度了。 - BitBank

使用 long 可能会提高性能，但这取决于不同的机器。有时候使用 int 会更好。 - Louis Wasserman

不幸的是，在我的情况下，将它们分组为long或int并没有好处，因为我需要在移位后获取此数组的摘要，并且MessageDigest对象需要一个字节数组，因此每次完成位移时都需要将longs解包成字节。 - mota

@phuclv 我不是以英语为母语的人，但根据维基百科的说法，循环移位（或者你所说的旋转）就是我想要的：https://en.wikipedia.org/wiki/Circular_shift - 这只是术语问题。我已经调整了标题以反映这一点。谢谢！ - mota

Answer 1

唯一的方法是进行彻底的基准测试，最快的实现方式将因平台而异。如果确实需要优化，请使用像Caliper这样的工具。

- Louis Wasserman

---

请问是否可以提供更多背景信息？这个问题的具体上下文有助于更好地理解。 - Louis Wasserman

Answer 2

你可以尝试的一件事是将 (byte[a]&0xff)>>b 替换为 byte[a]>>>b。

此外，在左移时不需要使用 &0xff。

虽然可能并不重要，但将 tmp 添加为 final 或将声明移到循环外部可能会稍微有所帮助。

另外一件事情是可以尝试：

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 [bytes.length-1]。

如果你迷信的话，那个反向循环也可能有帮助。我以前见过它起作用。

每次通过的循环分析：

你的：3个赋值，两个移位，一个或，一个转换。

我的：2个赋值，两个移位，一个或，一个转换。

- warren

---

(byte[a]&0xff)>>b 和 byte[a]>>>b 不等价！在前者中，左侧在移除高字节后被提升为 int，从而产生所需的结果。而在后者中，先进行提升，然后进行无符号移位，使得 a 左侧的位将成为 a 的符号位，然后再加上 b 个 0。 - TT--

Answer 3

如果您愿意，您可以将此推广到长整型和多个位移。

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

- Mike Dunlavey

Answer 4

使用ByteBuffer.wrap获取一个包装你的byte[]的缓冲区，然后使用ByteBuffer.asLongBuffer()获取一个视图，允许你提取和操作long，正如@NiklasB所建议的那样。从而利用硬件移动更大块的位的能力。

- Mike Samuel