代码之家 › 专栏 › 技术社区 › Peter

16位值中的非冗余位

shift bits boolean language-agnostic algorithm

Peter · 技术社区 · 17 年前

我有一个16位的值,其位“交错”。

第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 回复 | 直到 17 年前

Daniel Earwicker 17 年前

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

通过使用 for

Phil Miller 17 年前

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]
}

每个条目只有四个操作,而不是五个。诀窍在于重用移位的值。添加 slide + 这可能是一个弱点。

一个更大的弱点可能是,每个条目的操作必须完全按顺序完成,从进入处理器管道到离开处理器管道的延迟为4条指令。这些可以完全管道化,但仍会有一些延迟。该问题的版本公开了一些指令级并行性,并且如果有足够的执行资源,每个条目可能只有3条指令的延迟。

编辑:一种两次通过的方法,对称地处理低阶和高阶位,使用交错的0,将它们彼此偏移1,或者结果可能更快,并且可扩展到更长的位字符串。

编辑以更正错误根据佩德罗的评论。很抱歉占用你的时间在我可怜的基础转换技能上。原来是 0xef ,这会将0位放在错误的位置。

Peter 17 年前

这是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];
}

rsp 17 年前

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]
         ];
}