2

我有一个 16 位的值，它的位是“交错的”。

我想得到一个包含 8 个项目（值 0 到 3）的数组，它按以下顺序存储位：

  • 第 0 项：第 7 位和第 15 位
  • 第 1 项：第 6 位和第 14 位
  • 第 2 项：第 5 位和第 13 位
  • ...
  • 第 7 项：位 0 和 8

这是一个简单的解决方案：

function uninterlace(n) {
  return [((n>>7)&1)|((n>>14)&2), // bits 7 and 15
          ((n>>6)&1)|((n>>13)&2), // bits 6 and 14
          ((n>>5)&1)|((n>>12)&2), // bits 5 and 13
          ((n>>4)&1)|((n>>11)&2), // bits 4 and 12
          ((n>>3)&1)|((n>>10)&2), // bits 3 and 11
          ((n>>2)&1)|((n>> 9)&2), // bits 2 and 10
          ((n>>1)&1)|((n>> 8)&2), // bits 1 and 9
          ((n>>0)&1)|((n>> 7)&2)];// bits 0 and 8
}

有谁知道这样做更好（更快）的方法？

编辑：

笔记：

  • 构建预先计算的表不是一种选择。
  • 无法使用汇编程序或特定于 CPU 的优化
4

4 回答 4

1

比手写展开循环更快？我对此表示怀疑。

使用for-loop 可以减少代码的重复性，但这不会使其运行得更快。

于 2009-09-26T22:16:43.423 回答
1 
def uninterlace(n) {
    mask = 0x0101 // 0b0000_0001_0000_0001
    slide = 0x7f  // 0b0111_1111
    return [(((n >> 0) & mask) + slide) >> 7,
            (((n >> 1) & mask) + slide) >> 7,
            (((n >> 2) & mask) + slide) >> 7,
            (((n >> 3) & mask) + slide) >> 7,
            (((n >> 4) & mask) + slide) >> 7,
            (((n >> 5) & mask) + slide) >> 7,
            (((n >> 6) & mask) + slide) >> 7,
            (((n >> 7) & mask) + slide) >> 7]
}

每个条目只有四个操作，而不是 5 个。诀窍在于重用移位的值。相加slide将相关位彼此相邻移动，移位 7 将它们置于低位。的使用+可能是一个弱点。

一个更大的弱点可能是每个条目的操作必须完全按顺序完成，从进入处理器的管道到离开它会产生 4 条指令的延迟。这些可以完全流水线化，但仍然会有一些延迟。该问题的版本暴露了一些指令级并行性，并且在给定足够的执行资源的情况下，每个条目可能只有 3 条指令的延迟。

可能可以将多个提取组合成更少的操作，但我还没有看到一种方法来做到这一点。事实上，交错确实使这具有挑战性。

编辑：一种两遍方法来对称地处理低位和高位，使用交错的 0，将它们彼此移开一个，或者结果可能更快，并且可以扩展到更长的位串。

编辑以更正 Per slidePedro 的评论。很抱歉占用您的时间在我糟糕的基础转换技能上。它最初是0xef，它将 0 位放在错误的位置。

于 2009-09-26T22:42:04.153 回答
1

好的，现在每个项目有 3 个操作（经过测试和工作）。

这是 Novelocrat 答案的变体。它使用可变蒙版和幻灯片。

function uninterlace(n) {     
     return [((n & 0x8080) + 0x3FFF) >> 14,
             ((n & 0x4040) + 0x1FFF) >> 13,
             ((n & 0x2020) + 0x0FFF) >> 12,
             ((n & 0x1010) + 0x07FF) >> 11,
             ((n & 0x0808) + 0x03FF) >> 10,
             ((n & 0x0404) + 0x01FF) >> 9,
             ((n & 0x0202) + 0x00FF) >> 8,
             ((n & 0x0101) + 0x007F) >> 7];
}
于 2009-09-27T01:04:04.600 回答
0

一个预先计算好的 128 个条目乘以 2 的小表怎么样？

int[128] b1 = { 2, 3, 3, .. 3};
int[128] b0 = { 0, 1, 1, .. 1};

function uninterlace(n) {
  return [(n & 0x8000) ? b1 : b0)[n & 0x80],
          (n & 0x4000) ? b1 : b0)[n & 0x40],
          (n & 0x2000) ? b1 : b0)[n & 0x20],
          (n & 0x1000) ? b1 : b0)[n & 0x10],
          (n & 0x0800) ? b1 : b0)[n & 0x08],
          (n & 0x0400) ? b1 : b0)[n & 0x04],
          (n & 0x0200) ? b1 : b0)[n & 0x02],
          (n & 0x0100) ? b1 : b0)[n & 0x01]
         ];
}

这使用位掩码和表查找而不是移位和加法，并且可能更快。

于 2009-10-07T12:02:53.927 回答