3

我需要对 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

编辑：我在想一些类似的 东西

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

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

未找到解决方案。

4

4 回答 4

5

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

看到这里的小技巧

于 2009-03-09T01:54:26.550 回答
4

看看你的“天真”代码的编译器输出，它可能会让你大吃一惊。我曾经做过类似的事情，编译器（VC++2005）完全改变了我所有的值和移位，以提高它们的效率，例如我确信它会删除你的“（0x001＆In）>> 3"。

但是，是的，如果重新洗牌是一个固定功能，那么一张桌子可能是最好的。

更新

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

首先，我为“In”尝试了一个常量值，但编译器一点也没有被愚弄，它产生了以下代码：

mov eax,469h

IE。它完全优化了它。

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

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 - 对于六个输入来说还不错。可能比大多数人用手做的要好。

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

于 2009-03-08T23:30:47.193 回答
2

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

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

使用查找表:)

于 2009-03-08T23:30:23.840 回答
0

在优化之前，您应该确保您的“天真”方式正在按照您的意愿行事。如果我把你的代码变成一个函数并运行这个循环：

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 ;
于 2009-04-02T21:51:02.367 回答