位调整重新排序

Question

我需要对 7 位值进行任意重新排序（是的，我知道我应该使用表格），并且想知道是否有任何位黑客可以做到这一点。

示例：

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

---

编辑： 我正在考虑类似 this

只是为了好玩，因为我是 AFTK，所以我正在尝试强力搜索以下形式的解决方案：

((In * C1) >> C2) & 0x7f

未找到解决方案。

Answer 1

第一步似乎是理解数学解决方案并对其进行优化。

请参阅此处的位黑客

Answer 2

看看你的“天真的”代码的编译器输出，它可能会让你感到惊讶。 我曾经做过类似的事情，编译器（VC++2005）完全改变了我所有的 and 和移位的值，使它们更有效，例如我确信它会删除你的“（0x001 & In）> ；>3”。

但是，是的，如果重新洗牌是固定功能，那么表格可能是最好的。

更新

为了一笑，我查看了 VC++ 2005 的编译器输出......

首先，我尝试为“In”使用常量值，但编译器并没有被愚弄，它生成了以下代码：

mov eax,469h

即。 它完全优化了它。

所以......我尝试了一个正确的输入并得到了这个：

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx 

这是四个移位操作，五个AND，四个OR - 对于六个输入来说还不错。 可能比大多数人手工做的要好。

它可能还针对乱序执行进行了优化，因此时钟周期比看起来要少。 :-)

Answer 3

对于常见操作，有很多位旋转技巧，即反转 32 位字中的位顺序（移位、AND 和 OR 各 10 个，AFAICR）。

在这种情况下，从输入到输出的映射显然是完全任意的，我看不到任何清理它的方法。

使用查找表:)

Answer 4

在优化之前，您应该确保您的“天真的”方式正在按照您的意图进行。 如果我将您的代码放入一个函数并运行此循环：

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

它会产生此输出，这与注释相矛盾。 事实上，它会丢失比特。

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

为了获得您描述的随机播放，我会像这样编码：

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;