C MSB 到 LSB 解释

Question

有人可以向我解释一下该算法如何在 32 位系统上将 MSB 转换为 LSB 或将 LSB 转换为 MSB 吗？

unsigned char b = x;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

我以前在代码中见过以 LU 或 U 结尾的十六进制值，它们是什么意思？

谢谢!

Answer 1

据推测，一个 char有八位，所以 unsigned char b = x取 x 的低八位。

带有 0x22110 的掩码提取位 4、8、13 和 17(最低有效位从 0 开始编号)。因此，在乘以 0x0802 时，我们只关心它在这些位上的位置。在 0x802 中，第 1 位和第 11 位打开，因此此乘法放置了 b 的八位的副本。在位 1 到 8 中，另一个副本在位 11 到 18 中。没有重叠，因此在更一般的乘法中添加重叠的位不会产生任何影响。

从这个产品中，我们获取了这些位:

• 第 4 位，即 b 的第 3 位. (从第 1 位开始的副本的第 4 位，因此 b 的第 4–1 = 3 位。)
• 第 8 位，即 b 的第 7 位. (8–1 = 7.)
• 第 13 位，即 b 的第 2 位. (13–11 = 2.)
• 第 17 位，即 b 的第 6 位. (17–11 = 6.)

类似地，0x88440 的掩码提取位 6、10、15 和 19。与 0x8020 的乘法放置了 b 的副本。在位 5 到 12 中，另一个副本在位 15 到 22 中。我们从这个产品中获取这些位:

• 第 6 位，即 b 的第 1 位.
• 第 10 位，即 b 的第 5 位.
• 第 15 位，即 b 的第 0 位.
• 第 19 位，即 b 的第 4 位.

然后我们将它们或在一起，产生:

• 第 4 位，即 b 的第 3 位.
• 第 6 位，即 b 的第 1 位.
• 第 8 位，即 b 的第 7 位.
• 第 10 位，即 b 的第 5 位.
• 第 13 位，即 b 的第 2 位.
• 第 15 位，即 b 的第 0 位.
• 第 17 位，即 b 的第 6 位.
• 第 19 位，即 b 的第 4 位.

将此结果称为 t .

我们要把它乘以 0x10101，右移 16，然后赋值给 b .赋值转换为 unsigned char ，所以只保留低八位。移位后的低八位是移位前的第 24 位到第 31 位。所以我们只关心产品中的第 24 位到第 31 位。

乘数 0x10101 的位 0、8 和 16 已设置。因此，结果中的第 24 位是 t 中第 24、16 和 8 位之和。 ，加上来自其他地方的任何进位。但是，没有进位:观察 t 中没有任何设置位。相隔八个，就像乘法器中的位一样。因此，它们都不能直接贡献于产品中的相同位。乘积中的每一位最多是t中一位的结果.我们只需要弄清楚那是哪一位。

第 24 位必须来自 t 中的第 8、16 或 24 位.只能设置bit 8，它是b中的bit 7 .以这种方式推导所有位:

• 第 24 位是 t 中的第 8 位, 这是 b 中的第 7 位.
• 第 25 位是 t 中的第 17 位, 这是 b 中的第 6 位.
• 第 26 位是 t 中的第 10 位, 这是 b 中的第 5 位.
• 第 27 位是 t 中的第 19 位, 这是 b 中的第 4 位.
• 第 28 位是 t 中的第 4 位, 这是 b 中的第 3 位.
• 第 29 位是 t 中的第 13 位, 这是 b 中的第 2 位.
• 第 30 位是 t 中的第 6 位, 这是 b 中的位 1 .
• 第 31 位是 t 中的第 15 位, 这是 b 中的位 0 .

因此，乘积中的第 24 位到第 31 位是 b 中的第 7 位到第 0 位。 ，所以最终产生的八位是b中的第7到0位.