1

我正在查看下面的位反转代码，只是想知道如何想出这些东西。（来源：http ://www.cl.cam.ac.uk/~am21/hakmemc.html ）

/* reverse 8 bits (Schroeppel) */
unsigned reverse_8bits(unsigned41 a) {
  return ((a * 0x000202020202)  /* 5 copies in 40 bits */
             & 0x010884422010)  /* where bits coincide with reverse repeated base 2^10 */
                                /* PDP-10: 041(6 bits):020420420020(35 bits) */
             % 1023;            /* casting out 2^10 - 1's */
}

有人可以解释评论“位与反向重复基数 2^10 重合”是什么意思吗？另外“%1023”如何提取相关位？这有什么一般的想法吗？

4

2 回答 2

3

你问的是一个非常广泛的问题。

以下是对% 1023可能内容的解释：您知道计算n % 9是如何将 的以 10 为基数的表示的数字相加的n吗？例如，52 % 9 = 7 = 5 + 2。您问题中的代码使用 1023 = 1024 - 1 而不是 9 = 10 - 1 做同样的事情。它使用该操作% 1023来收集已计算的多个结果“独立”作为大量的 10 位切片。

这是关于如何选择常量0x000202020202和的线索的开始0x010884422010：它们使宽整数运算在大数的 10 位切片上作为独立的更简单运算进行操作。

于 2013-08-02T07:15:07.250 回答
1

扩展 Pascal Cuoq 的想法，这里有一个解释。

一般的想法是，在任何基数中，如果任何数字除以（基数-1），余数将是该数字中所有数字的总和。

例如，34 除以 9 后余数为 7。这是因为 34 可以写成 3 * 10 + 4

即 34 = 3 * 10 + 4 = 3 * (9 +1) + 4 = 3 * 9 + (3 +4)

现在，9 除以 3 * 9，余数为 (3 + 4)。这个过程可以扩展到任何基数'b'，因为 (b^n - 1) 总是除以 (b-1)。

现在，问题来了，如果一个数字以 1024 为基数，如果该数字除以 1023，则余数将是其数字的总和。

要将二进制数转换为基数 1024，我们可以将右侧的 10 位分组为单个数字

例如，要将二进制数 0x010884422010(0b10000100010000100010000100010000000010000) 转换为基数 1024，我们可以将其分组为 10 位数字，如下所示

(1) (0000100010) (0001000100) (0010001000) (0000010000) = 
(0b0000000001)*1024^4 + (0b0000100010)*1024^3 + (0b0001000100)*1024^2 + (0b0010001000)*1024^1 + (0b0000010000)*1024^0

因此，当这个数字除以 1023 时，余数的总和为

  0b0000000001
+ 0b0000100010
+ 0b0001000100
+ 0b0010001000
+ 0b0000010000
--------------------
  0b0011111111

如果您仔细观察上述数字，则上述每个数字中的“1”位占据互补位置。因此，当加在一起时，它应该拉出原始数字中的所有 8 位。

因此，在上面的代码中， , 创建了字节“ a"a * 0x000202020202" ”的 5 个副本。当结果与 进行 AND 运算时，我们有选择地在“ a ”的 5 个副本中选择 8 位。当应用“ ”时，我们拉出所有 8 位。0x010884422010% 1023

那么，它实际上是如何反转位的呢？这有点聪明。这个想法是，数字 0b0000000001 中的“1”位实际上与原始字节的 MSB 对齐。因此，当您“与”时，您实际上是在将原始字节的 MSB 与幻数数字的 LSB 进行与运算。类似地，数字 0b0000100010 与 MSB 的第二和第六位对齐，依此类推。

因此，当您添加幻数的所有数字时，生成的数字将与原始字节相反。

于 2013-08-02T10:08:43.340 回答