3

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

因此，为了解决这样的问题，我将其最小化为一个问题：我必须执行哪些步骤才能仅使用 4 位来旋转 32 位数字。好吧，如果您考虑一下，它是一个 32 位数字，包含 8 组，每组 4 位，因此如果要旋转的位数是 4，那么组之间会发生交换0 and 4，1 and 5, 2 and 6, 3 and 7, 之后旋转完成。

如果要旋转的位小于 4 且大于 0，那么很简单，只需保留最后一位N并开始移位或循环，例如，假设我们有将0x9CE2其左旋转 3 位的数字，我们将执行以下操作：

little endian 二进制中的数字是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以十六进制表示，这是正确的答案；并且，如果您尝试以任何精度将其应用于任何数字，您所需要的只是一个变量，该变量的类型是形成该 bignum 类型的数组的任何元素的类型。

现在真正的问题是当要旋转的位数大于一组或大于类型的一半时（即在此示例中大于 4 位或 8 位）。

通常，我们将位从最后一个元素移到第一个元素，依此类推；但是现在，在将最后一个元素移动到第一个元素之后，结果必须重新定位到新的位置，因为要旋转的位数大于元素上的位数（即> 4 bits）。移位开始的起始索引是最后一个索引（本例中为 3），对于目标索引，我们使用dest_index = int(bits_count/half_bits) + 1等式：第一次移位的结果必须重新定位到目标索引 2——这是我的问题，因为我想不出一种方法来为这种情况编写算法。half_bitshalf_bits = 8bits_count = 7dest_index = int(7/8) + 1 = 1 + 1 = 2

谢谢。

4

2 回答 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 项存储开销来进行轮换，那么要旋转 3 项，您可能会这样处理它：

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

你可以做一个优化来避免每次迭代的交换，我将把它作为练习。

于 2012-06-10T23:55:03.373 回答
2

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

许多汇编语言具有更好的通过进位旋转位和通过位旋转进位的工具。

很多时候，汇编语言不如 C 或 C++ 函数复杂。

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

于 2012-06-11T02:05:32.433 回答