Bit twiddling:设置了哪个位？

Question

我有一个64位无符号整数,正好设置了1位.我想为每个可能的64个值分配一个值(在这种情况下,奇数素数,因此0x1对应于3,0x2对应于5,...,0x8000000000000000对应于313).

似乎最好的方法是转换1 - > 0,2 - > 1,4 - > 2,8 - > 3,...,2 ^ 63 - > 63并查找数组中的值.但即使如此,我也不确定获得二进制指数的最快方法是什么.并且可能还有更快/更好的方法.

此操作将使用10 ¹⁴到10 ¹⁶次,因此性能是一个严重的问题.

Answer 1

最后是最佳解决方案.请参阅本节末尾,确保输入确保只有一个非零位时:http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn

这是代码:

static const int MultiplyDeBruijnBitPosition2[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];

您可以将其调整为基于直接乘法的64位输入算法; 否则,只需添加一个条件以查看该位是在高32位还是低32位,然后在此处使用32位算法.

更新:这是我自己开发的至少一个64位版本,但它使用了除法(实际上是模数).

r = Table[v%67];

对于2的每个幂,v%67具有不同的值,所以只需将奇数素数(或者如果你不想要奇数素数的位指数)放在表中的正确位置.不使用3个位置(0,17和34),如果您还想接受所有位零作为输入,这可能很方便.

更新2:64位版本.

r = Table[(uint64_t)(val * 0x022fdd63cc95386dull) >> 58];

这是我原来的作品,但是我从这个国际象棋网站上得到了B(2,6) De Bruijn序列,所以除了弄清楚De Bruijn序列是什么以及使用谷歌之外我什么都不值得.;-)

关于其工作原理的一些补充说明:

神奇的数字是B(2,6)De Bruijn序列.它的特性是,如果你看一个6连续的位窗口,你可以通过适当地旋转数字来获得该窗口中的任何六位值,并且通过恰好一次旋转获得每个可能的六位值.

我们将有问题的窗口固定为前6位位置,并选择前6位中带有0的De Bruijn序列.这使得我们永远不必处理位旋转,只需要移位,因为0将自然地进入底部位(并且我们永远不会在最高6位窗口中从底部查看超过5位) .

现在,该函数的输入值是2的幂.因此,将De Bruijn序列乘以输入值会按log2(value)比特执行比特移位.我们现在在高6位中有一个数字,该数字唯一地确定我们移位了多少位,并且可以将其用作表的索引以获得移位的实际长度.

只要您愿意实现乘法,这种方法可以用于任意大或任意小的整数.你只需要找到一个B(2,k)De Bruijn序列,其中k是位数.我上面提供的国际象棋维基链接的De Bruijn序列的值k范围从1到6,而一些快速的谷歌搜索显示有一些关于在一般情况下生成它们的最佳算法的论文.

Answer 2

如果性能是一个严重的问题,那么你应该使用intrinsics/builtins来使用CPU特定的指令,例如这里为gcc找到的指令:

http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html

- 内置函数:int __builtin_ffs (unsigned int x) 返回一个加上x的最低有效1位的索引,或者如果x为零,则返回零.

- 内置函数:int __builtin_clz (unsigned int x) 从最高位开始,返回x中前导0位的数量.如果x为0,则结果未定义.

- 内置函数:int __builtin_ctz (unsigned int x) 从最低有效位开始,返回x中的尾随0位数.如果x为0,则结果未定义.

像这样的东西是许多O(1)算法的核心,例如内核调度程序,它需要找到由位数组表示的第一个非空队列.

注意:我已经列出了unsigned int版本,但gcc也有unsigned long long版本.

Answer 3

您可以使用二进制搜索技术:

int pos = 0;
if ((value & 0xffffffff) == 0) {
    pos += 32;
    value >>= 32;
}
if ((value & 0xffff) == 0) {
    pos += 16;
    value >>= 16;
}
if ((value & 0xff) == 0) {
    pos += 8;
    value >>= 8;
}
if ((value & 0xf) == 0) {
    pos += 4;
    value >>= 4;
}
if ((value & 0x3) == 0) {
    pos += 2;
    value >>= 2;
}
if ((value & 0x1) == 0) {
    pos += 1;
}

这比循环已经展开的循环具有优势.但是,如果这对性能至关重要,您将需要测试和测量每个提议的解决方案.

Answer 4

有些架构(实际上是一个惊人的数字)只有一条指令可以进行你想要的计算.在ARM上,它将是CLZ(计数前导零)指令.对于intel,BSF(位扫描正向)或BSR(位扫描反向)指令可以帮助你.

我想这不是一个真正的C答案,但它会让你获得所需的速度!