是否有一种算法可以在不溢出的情况下将数字中的每 n 个长位移位？

Question

例如，如果我有一个数字 0101 1111，我想将每 4 位长的部分向左移动以获得 1010 1110。虽然我可以对每个部分取模以获得两个 4 位数字，但是否有不需要这样做的算法？

Answer 1

一种天真的方法

第一个天真的方法是分割 4 个位组并单独处理它们。对于第一组 4 位，使用以下方法获得预期结果。

(((x & 0xf)          // take only 4 bits
    << 1)            // shift them by 1
       & 0xf)        // get rid of potential overflow

第n+1组4位为

(((x & (0xf<<(n*4)))
    << 1)
      & (0xf<<(n*4)))

由于这是设计的，因此处理的 4 位周围没有重叠，您可以迭代，binary-or 部分结果。

一种不那么幼稚的方法

另一种方法是简单地将完整的 x 移位 1，导致每 4 位组一次移位：

0101 1111  -> 1011 1110

然后我们可以轻松消除溢出，同时通过清除移位结果中的每 4 位来确保在左侧注入 0：

   1011 1110 
 & 1110 1110
   ---------
   1010 1110

1110 是十六进制的 e。因此，您需要生成一个 0xe 与 4 位段一样多的数字。在您的情况下，如果它只是 8 位，则为 0xee。如果是 64 位，则为 0xeeeeeeeeeeeeeeee。有人在评论中告诉了这个答案。这里有解释。

注意如果你的底层数据类型是有符号的，因为有符号位。对无符号整数执行此处理以避免任何意外。

Answer 2

这是一种方法。

int bits = 0b1111_0001_0011_0111;
int result = 0;
int m = 0b1111;
while(m != 0) {
    result |= ((bits & m) << 1) & m;
    m <<= 4;
}
System.out.printf("%-7s = %s%n","src", Integer.toBinaryString(bits));
System.out.printf("%-7s = %s%n","result", Integer.toBinaryString(result));

版画

src     = 1111000100110111
result  = 1110001001101110

是否有一种算法可以在不溢出的情况下将数字中的每 n 个长位移位？

Is there an algorithm to bit shift every n-long bits from a number without overflow?

algorithm

bit-manipulation

一种天真的方法

一种不那么幼稚的方法