haskell - 如何将所有零移掉？

Question

这是 my last question 的后续内容。我成功地实现了一个相当快的“位队列生成器”

data BitQueueB = BQB !Word !Word

通过从左侧插入元素(从保护位开始)，然后当我完成“构建”队列时，计算尾随零并将其移开，在左侧安装一个新的保护位。

但是，此解决方案对于 GHC < 7.10 并没有真正做任何事情，因为那是引入 countTrailingZeros 的时候。我也忍不住想知道是否有一些更神奇的方法来完成这种转变，或者是向左的对应。

要点

我有一个双字的两个字表示，保证至少设置了一位。我正在寻找最快的方法将双字移至左侧或右侧，直到第一个设置位被移走，而不使用 countLeadingZeros 或 countTrailingZeros.

一个想法

我在这些问题上的糟糕直觉表明，如果我切换到左移，是否可以通过某种方式使用乘法，但也许这只是一厢情愿的想法。

Answer 1

左边更烦人。未实际测试:

m = x
m |= m >> 1
m |= m >> 2
m |= m >> 4
m |= m >> 8
m |= m >> 16
x = x * (0x80000000 / (m >> 1))

首先计算数字中存在的 2 的最高幂，然后乘以将其转换为 2 的最高可能幂所需的量，从而将最高设置位移动到顶部。它不喜欢最高位已经设置(它会除以 0)并且需要知道位数。因此，最好只计算前导零而不是这个，或者也许有更好的东西，但我不知道。

右边的版本(为了完整性？)更好，只是

x / (x & -x)

其中x & -x是一个相对众所周知的隔离最低设置位的技巧。