大整数位旋转

Question

大整数位旋转

3

我想在我的整数类中实现无符号左旋转。但由于它是一个模板类，可以是任何大小，从128位到更大；因此，我不能使用需要相同大小的临时变量的算法，因为如果类型变得很大，就会发生堆栈溢出（特别是如果这样的函数在调用链中）。

因此，为了解决这个问题，我将其缩小为一个问题：仅使用4位，我必须执行哪些步骤才能旋转32位数字。好吧，如果你考虑一下，一个32位数字包含8组每组4位，因此如果要旋转的位数为4，则将在组0和4，1和5，2和6，3和7之间进行交换，然后进行旋转。

如果要旋转的位数小于4且大于0，则只需保留最后的N位并开始移位或循环。例如，假设我们有数字0x9CE2，要向左旋转3位，则应按如下方式操作：

以小端二进制表示的数字为1001 1100 1110 0010，每个四位数从右到左编号为0到3，我们将称此数字为N，一组中的位数为B。

[1] x <- N[3] >> 3
    x <- 1001 >> 3
    x <- 0100

    y <- N[0] >> (B - 3)
    y <- N[0] >> (4 - 3)
    y <- 0010 >> 1
    y <- 0001

    N[0] <- (N[0] << 3) | x
    N[0] <- (0010 << 3) | 0100
    N[0] <- 0000 | 0100
    N[0] <- 0100


[2] x <- y
    x <- 0001

    y <- N[1] >> (B - 3)
    y <- N[1] >> (4 - 3)
    y <- 1110 >> 1
    y <- 0111

    N[1] <- (N[1] << 3) | x
    N[1] <- (1110 << 3) | 0001
    N[1] <- 0000 | 0001
    N[1] <- 0001


[3] x <- y
    x <- 0111

    y <- N[2] >> (B - 3)
    y <- N[2] >> (4 - 3)
    y <- 1100 >> 1
    y <- 0110

    N[2] <- (N[2] << 3) | x
    N[2] <- (1100 << 3) | 0111
    N[2] <- 0000 | 0111
    N[2] <- 0111


[4] x <- y
    x <- 0110

    y <- N[3] >> (B - 3)
    y <- N[3] >> (4 - 3)
    y <- 1001 >> 1
    y <- 0100

    N[3] <- (N[3] << 3) | x
    N[3] <- (1001 << 3) | 0110
    N[3] <- 1000 | 0110
    N[3] <- 1110

结果是1110 0111 0001 0100，十六进制为0xE714，这是正确的答案；如果您尝试将其应用于任何具有任何精度的数字，则所需的仅是一个类型为形成该大数类型的数组中的任何元素类型的变量。

现在真正的问题是当要旋转的位数大于一个组或大于类型的一半大小时（即大于4位或8位），情况就很复杂了。

通常，我们从最后一个元素向第一个元素移位，以此类推；但现在，在将最后一个元素移动到第一个元素之后，结果必须被重新定位到新位置，因为要旋转的位数大于一个元素（即> 4位）。移位将开始的起始索引是最后一个索引（在此示例中为3），对于目标索引，我们使用方程式：dest_index = int(bits_count/half_bits) + 1，其中half_bits是数字的一半位数，在此示例中half_bits = 8，因此如果bits_count = 7，则dest_index = int(7/8) + 1 = 1 + 1 = 2，这意味着第一次移位的结果必须重新定位到目标索引2 - 这就是我的问题，因为我无法想出一种算法来解决这种情况。

谢谢。

- Muhammad

2个回答

2

这只是一种实现方式的提示。您可以考虑进行两次旋转。

第一次旋转，仅在4位边界上旋转
第二次旋转，仅在1位边界上旋转

因此，顶层伪代码可能如下所示：

rotate (unsigned bits) {
  bits %= 32; /* only have 32 bits */
  if (bits == 0) return;
  rotate_nibs(bits/4);
  rotate_bits(bits%4);
}

因此，要旋转13位，您首先要旋转3个半字节，然后再旋转1位，以获得总共13位的旋转。

如果您将半字节数组视为循环缓冲区，则完全可以避免半字节旋转。然后，半字节旋转只是更改0索引在数组中的起始位置的问题。

如果必须进行旋转，则可能会有些棘手。如果要旋转8项数组，并且只想使用1项存储开销来执行旋转，则可能会这样处理：

   orig: A B C D E F G H
 step 1: A B C A E F G H  rem: D
      2: A B C A E F D H  rem: G
      3: A G C A E F D H  rem: B
      4: A G C A B F D H  rem: E
      5: A G C A B F D E  rem: H
      6: A G H A B F D E  rem: C
      7: A G H A B C D E  rem: F
      8: F G H A B C D E  done

但是，如果您尝试使用2、4或6个项目进行旋转，循环将无法通过整个数组运行。因此，必须注意旋转计数和数组大小是否具有公共除数，并使算法考虑到这一点。如果您使用6步旋转逐步执行，则会出现更多线索。

   orig: A B C D E F G H
                     A
                 G
             E
         C                 cycled back to A's position
                       B
                   H
               F
           D               done

请注意，GCD(6,8)是2，这意味着我们每次遍历应该期望4次迭代。然后，N项数组的旋转算法可能如下所示：

rotate (n) {
  G = GCD(n, N)
  for (i = 0; i < G; ++i) {
    p = arr[i];
    for (j = 1; j < N/G; ++j) {
      swap(p, arr[(i + j*n) % N]);
    }
    arr[i] = p;
  }
}

有一种优化方法可以避免每次迭代的交换，我会留作练习。

- jxh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas Matthews · Accepted Answer

我建议调用汇编语言函数进行位旋转。

许多汇编语言都有更好的功能来通过进位旋转位和通过位旋转进位。

很多时候，汇编语言比C或C++函数更简单。

缺点是你需要为每个{不同的}平台准备一个实例的汇编函数。