3

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

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

我之前在代码中看到十六进制值以 LU 或只是 U 结尾，它们是什么意思？

谢谢！

4

4 回答 4

3

据推测，achar有 8 位，所以unsigned char b = x取 x 的低 8 位。

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

从这个产品中，我们得到了这些位：

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

类似地，掩码 0x88440 提取位 6、10、15 和 19。乘以 0x8020b在位 5 到 12 中放置一个副本，在位 15 到 22 中放置另一个副本。从这个产品中，我们得到这些位：

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

然后我们将它们组合在一起，产生：

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

调用这个结果t。

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

乘法器 0x10101 设置了位 0、8 和 16。因此，结果中的第 24 位是 中的第 24、16 和 8 位的总和t，加上来自其他地方的任何进位。但是，没有进位：请注意，没有一个设置位t相隔 8 位，就像乘法器中的位一样。因此，它们中的任何一个都不能直接对产品中的同一位做出贡献。乘积中的每一位是 中最多一位的结果t。我们只需要弄清楚那是哪一点。

第 24 位必须来自第 8、16 或 24 位t。只能设置第 8 位，它是来自 的第 7 位b。以这种方式推断所有位：

  • 第 24 位是第 8 位t，也就是第 7 位b。
  • 第25 位是第 17 位t，也就是第 6 位b。
  • 第26 位是第 10 位t，也就是第 5 位b。
  • 第27 位是第 19 位t，也就是第 4 位b。
  • 第 28 位是第 4 位t，也就是第 3 位b。
  • 第 29 位是第 13 位t，也就是第 2 位b。
  • 第 30 位是第 6 位t，也就是第 1 位b。
  • 第 31 位是第 15 位t，也就是第 0 位b。

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

于 2013-08-22T00:28:27.160 回答
3

将 b 视为一个 8 位值abcdefgh，其中每个字母都是单个位（0 或 1），具有a最高有效位和h最低有效位。然后看看每个操作对这些位做了什么：

b * 0x0802LU             = 00000abcdefgh00abcdefgh0 
b * 0x0802LU & 0x22110LU = 000000b000f0000a000e0000
b * 0x8020LU             = 0abcdefgh00abcdefgh00000
b * 0x8020LU & 0x88440LU = 0000d000h0000c000g000000
((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU))
                         = 0000d0b0h0f00c0a0g0e0000

所以在这一点上，它已经对位进行了洗牌并将它们分散开来。

(....) * 0x10101LU       =                 d0b0h0f00c0a0g0e0000
                         +         d0b0h0f00c0a0g0e000000000000
                         + d0b0h0f00c0a0g0e00000000000000000000
                         = d0b0f0f0dcbahgfedcbahgfe0c0a0g0e0000
(...) * 0x10101LU >> 16  = d0b0f0f0dcbahgfedcba
b                        = hgfedcba

乘法等效于移位/加法/加法（常量中设置了 3 位），它将位排列在它们应该结束的位置。然后最后的移位和减少到 8 位给你最终的位反转结果。

于 2013-08-22T00:38:00.647 回答
0

当您将其视为乘法和十六进制时，很难想象该算法在做什么。当您将其转换为二进制并将乘法替换为等效的移位运算总和时，它会变得更加清晰。本质上，它正在做的是通过移位和屏蔽字节来扩展部分字节，然后实现一个并行半加器来重建原位的部分，这恰好与它们开始的位置相反。

例如，

b * 0x0802 = b << 11 | b << 1

为 b 插入一些值（二进制）并继续。

于 2013-08-22T00:13:08.817 回答
0

要回答您的第二个问题，u意味着将十六进制常量视为无符号（如果需要将其扩展为更长的宽度），并且l意味着将其视为long.

我正在处理你的第一个问题。

于 2013-08-21T22:54:07.910 回答