algorithm - 位排列的通用算法

Question

是否有创建高效位排列算法的通用策略？目标是创建一种快速的无分支且可能的话无 LUT 的算法。我举个例子:

一个13位代码按照下面的规则表转换为另一个13位代码:

<表类=“s-表”> <标题> 位 输入(十月) 输入(BIN) 输出(BIN) 输出(十月) <正文> 0 1 0000000000001 0000100000000 256 1 2 0000000000010 0010000000000 1024 2 4 0000000000100 0100000000000 2048 3 8 0000000001000 1000000000000 4096 4 16 0000000010000 0000001000000 64 5 32 0000000100000 0000000100000 32 6 64 0000001000000 0001000000000 512 7 128 0000010000000 0000000010000 16 8 256 0000100000000 0000000001000 8 9 512 0001000000000 0000000000010 2 10 1024 0010000000000 0000000000001 1 11 2048 0100000000000 0000000000100 4 12 4096 1000000000000 0000010000000 128

示例:如果输入代码为 1+2+4096=4099，则结果输出将为 256+1024+128=1408

一个简单的方法是:

OUTPUT = ((INPUT AND 0000000000001) << 8) OR ((INPUT AND 0000000000010) << 9) OR ((INPUT AND 0000000000100) << 9) OR ((INPUT AND 0000000001000) << 9) OR ...

这意味着对于上面的示例，我们每个位有 3 条指令(AND、SHIFT、OR)= 39-1(最后一个 OR 省略)指令。相反，我们还可以使用左移和右移的组合来潜在地减少代码大小(取决于目标平台)，但这不会减少指令量。

在检查示例表时，您当然会注意到一些明显的优化可能性，例如在第 2/3/4 行中，可以将其组合为 ((INPUT AND 0000000000111) << 9) 。但除此之外，这正在成为一项艰巨而乏味的任务。

是一般策略吗？我认为使用卡诺-维奇图来简化表达式可能是一种方法？然而对于 13 个输入变量来说这是相当困难的。而且结果表达式只能是 OR 和 AND 的组合。

Answer 1

对于位排列，已知有几种在某些情况下有效的策略。 https://programming.sirrida.de/calcperm.php 有一个代码生成器它实现了其中的大部分。然而，在这种情况下，它似乎只能基本上找到您建议的策略，这表明在这种排列中似乎很难找到任何可利用的模式。