0

我正在尝试制作一个Inverse Multiplexer，它可以根据一些掩码将一个比特流分成许多。

这是想法示例

这是一个 24 位流，每个字母代表 1 位：

abcdefgh ijklmnop qrstuvwx

给定三个掩码，每个掩码没有共同点，如果 & 一起它们是 [1,1,1,1,1,1,1,1]

[1, 1, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 0, 0]

像这样将这些掩码应用于流

stream1 = ab__e___ ij__m___ qr__u___
stream2 = __c___gh __k___op __s___wx
stream3 = ___d_f__ ___l_n__ ___t_v__

所以原始比特流被分成三个比特流，如下所示：

stream1 = abeijmqru
stream2 = cghkopswx
stream3 = dflntv

以上只是一个例子，我需要对给定的比特流应用任意数量的掩码。面具是保证的，彼此之间OR，有零的结果。应用AND到所有掩码的结果为 ONE。所有面具的长度相同。

我写了一个愚蠢的版本来蛮力这个想法，它基本上是在一个循环中逐位移动。认为它肯定没有效率。

我查看了这个http://graphics.stanford.edu/~seander/bithacks.html

没有线索。任何人都有更好的想法如何改善这一点？（在 x86 机器上）

4

2 回答 2

1

如果每个位只映射到一个输出流，我认为定义这些位分配给哪些输出流比使用掩码更有意义。例如，您的示例掩码

[1, 1, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1, 1]
[0, 0, 0, 1, 0, 1, 0, 0]

而是表示为输出流以将当前位分配给

[0, 0, 1, 2, 0, 2, 1, 1]

还有一些伪代码将它们联系在一起

stream_order = [0, 0, 1, 2, 0, 2, 1, 1]
index = 0
for bit in input_stream:
    n = stream_order[index]
    output_streams[n].push(bit)
    index++
    index %= len(stream_order)
于 2013-11-28T04:31:15.613 回答
1

我想既然你只有一个对应于单个“流”的位，那么你可以同时移动所有这些并查看“这属于哪个流”。这将允许适度数量的并行实现——尽管这将在一定程度上取决于架构和掩码的大小，这将是多么有效。它还取决于您希望执行此操作的频率 - 一定数量的预计算将使后续运行更有效率。听起来确实有点蛮力。可能不会比你已经做过的更好。

当然，有一个可爱的问题Extracting bits with a single multiplication（我写了公认的答案……），它提出了一种通过单次乘法从更大的数中提取某些位的方法。这种方法确实有一个缺点，即您不能对任意数量的设置位执行此操作 - 两者之间需要有多个空格。

原则上，这可以通过重复该过程两次或更多次并在其间应用额外的掩码来解决。让我们看看这仅适用于上述问题中的第一个掩码。

mask1 = 11001000
num =   abcdefgh
temp = num & mask1 = ab..e...
magic = 4 + 1
answer =     ab..e... 
           ab..e..... + 
           ------------
           ababe.e...
mask2 =    0011100000
ans & mask = abe.....

这会将您想要的三个数字放在掩码乘掩码的前三个位置（3 次操作）。对于八位数字来说效率不是很高；但是您可以将其扩展为 32 位数字，然后它开始看起来更有趣。

于 2013-11-28T04:31:44.437 回答