c：位反转逻辑

我正在查看下面的位反转代码，只是想知道如何提出这些事情。 （来源： 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 % 9的基数为10的数字进行求和？ 例如，52％9 = 7 = 5 + 2.您的问题中的代码执行相同的操作1023 = 1024 – 1而不是9 = 10 – 1.它使用操作% 1023来收集多个结果被“独立地”计算为大数的10位切片。

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

Answer 2

扩展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 * 0x000202020202" ，创建了5个字节“ a ”的副本。 当结果与0x010884422010进行AND运算时，我们有选择地在5个“ a ”副本中选择8位。 当应用“ % 1023 ”时，我们拉出所有8位。

那么，它实际上如何反转位？ 那有点聪明。 想法是，数字0b0000000001中的“1”位实际上与原始字节的MSB对齐。 所以，当你“和”并且你实际上正在使用幻数位数的LSB对原始字节的MSB进行AND运算。 类似于数字0b0000100010与来自MSB的第二和第六位对齐，依此类推。

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