c:位反转逻辑

Question

我在看下面的位反转代码，只是想知道是如何产生这些东西的。(资料来源：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"是如何提取相关位的？这里面有什么一般性的想法吗？

Answer 1

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

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

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

Answer 2

扩展Pascal思想，这里是一个解释。

一般的思想是，在任何基中，如果任何数字除以(基-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 * 0x000202020202"创建了5个字节"a“的副本。当结果是ANDed和0x010884422010时，我们选择在"a“的5个副本中选择8位。当应用"% 1023“时，我们提取所有的8位。

那么，它是如何逆转比特的呢？这有点聪明。这个想法是，数字0b00000001中的"1“位实际上与原始字节的MSB对齐。所以，当你的“和”，你实际上是ANDing的原始字节与幻数数字的LSB。类似地，数字0b0000100010与MSB等的第二位和第六位对齐。

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