位操作：哪一位被设置了？

Question

位操作：哪一位被设置了？

cbit-manipulation

35

我有一个64位的无符号整数，恰好只有1个二进制位是1。我想为这64个可能的值（在这种情况下是奇素数，所以0x1对应3，0x2对应5，...，0x8000000000000000对应313）分配一个值。

看起来最好的方法是将1 → 0，2 → 1，4 → 2，8 → 3，...，2⁶³ → 63进行转换，并在数组中查找值。但即使是这样，我也不确定获得二进制指数的最快方法是什么。可能还有更有效的方法。

这个操作将会被使用10¹⁴到10¹⁶次，因此性能是一个严重问题。

- Charles

10

这个操作将被执行10的14次到10的16次，所以性能是一个严重的问题。很好！仅因此加1分。 - Will A

这基本上与https://dev59.com/UnA75IYBdhLWcg3weZDu相同。 - ergosys

2

最快的方法可能需要特定于CPU的指令。 - dreamlax

如果您可以保证恰好有一个位被设置，那么可能存在只涉及单个（整数）乘法或乘法和表查找的解决方案。我得考虑一下，或者也许别人会先想到它。 - R.. GitHub STOP HELPING ICE

我刚刚在著名的“位操作页面”上找到了它。请查看下面我的最新答案。 - R.. GitHub STOP HELPING ICE

15个回答

36

如果性能是一个严重的问题，那么你应该使用内建函数/内嵌汇编来使用CPU特定的指令，例如在这里找到的GCC指令：http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html 以下是一些内建函数的例子：

- 内建函数 int __builtin_ffs(unsigned int x)。返回x中最低位1的索引加1，如果x为0，则返回0。

- 内建函数 int __builtin_clz(unsigned int x)。返回x中从最高位开始的前导0位数。如果x为0，则结果未定义。

- 内建函数 int __builtin_ctz(unsigned int x)。返回x中从最低位开始的后缀0位数。如果x为0，则结果未定义。

这些类似的指令是许多O(1)算法的核心，例如内核调度程序需要查找由位数组表示的第一个非空队列。

请注意：我列出了无符号整数版本，但是GCC也有无符号长整型版本。

- Evan Teran

是的，这就是你应该这样做的方式。 - Matt Joiner

1

MSVC的等效物将是BitScanForward64和BitScanReverse64内部函数，还有一些版本适用于两者都不支持的系统，可以在这里找到：http://chessprogramming.wikispaces.com/BitScan - Necrolis

有没有某个页面可以解释不同芯片对应哪些指令映射到处理器指令，哪些使用库调用？ - Charles

这个页面（http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Target-Builtins.html#Target-Builtins）列出了特定目标的内建函数。我**假设**我在回复中提供的链接上的那些函数在所有支持的平台上都可用，因为它们没有指定体系结构。我认为，对于大多数情况，它们不依赖库调用（如果有的话），最坏的情况下只会在使用时放置一些内联代码。但是直到您测试或某些文档明确说明之前，您无法确定。 - Evan Teran

15

你可以使用二分查找技术：

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

相比于循环，这种方法的优势在于循环已经展开了。然而，如果性能真的很关键，你需要测试和测量每个提出的解决方案。

- ggg

很好的干净的实现。你也可以将其作为循环（使用固定次数的迭代），让编译器有可能展开。 - R.. GitHub STOP HELPING ICE

6

一些架构（实际上不少）拥有可以完成所需计算的单个指令。在 ARM 上，它将是 CLZ（计算前导零位数）指令。对于英特尔处理器，BSF（位扫描正向）或 BSR（位扫描反向）指令将帮助您达到所需速度。

我猜这并不是一个真正的 C 语言答案，但它会让您得到所需的速度！

- Carl Norum

2

预先计算1 << i (i = 0..63) 并将它们存储在数组中
使用二分查找来找到给定值的索引
使用此索引在另一个数组中查找素数

与我在这里发布的其他答案相比，这只需要6个步骤就可以找到索引（而不是最多64个步骤）。但我不确定这个答案的某一步是否比仅进行位移和递增计数器更耗时。您可能需要尝试两种方法。

- Andre Holzner

+1 用于二分查找，但要考虑到解决方案可能比仅仅移位慢。也许这个问题需要使用 __asm {} 来获得纯速度。 - Will A

3

赞成使用二分查找，但反对认为你需要一个数组来执行二分查找的荒谬想法。你可以直接在变量上执行二分查找，这样实际上会更快速。 - R.. GitHub STOP HELPING ICE

2

请参考http://graphics.stanford.edu/~seander/bithacks.html，特别是“查找整数的以2为底的对数（也称最高位集合的位置）”部分，了解一些替代算法。如果您非常注重速度，可以考虑放弃使用C语言，而选择使用CPU具有专用指令的语言。

- Tony Delroy

2

由于速度很重要，所以以下是一个疯狂的想法：

w1 = 第一组16位
w2 = 第二组16位
w3 = 第三组16位
w4 = 第四组16位

结果 = 数组1[w1] + 数组2[w2] + 数组3[w3] + 数组4[w4]

其中数组1到4是稀疏填充的64K数组，包含实际的质数值（在不对应位位置处为零）。

- Andrew

1

或者更好的是，result = array1[v&(1<<22)-1] + array2[v>>22&(1<<22)-1] + array3[v>>44]; 在这样的大小下，即使在物理内存中，数组也会是稀疏的，即大部分虚拟内存只是对零页的引用。 - R.. GitHub STOP HELPING ICE

2

请注意，由于 v 的值仅限于 64 种可能性，整个表格数据集应该适合 L2 缓存，甚至可能在 L1 缓存中。此外，由于您只关心 2 的幂输入，因此可以安排所有 4/所有 3 数组占用重叠空间。 - R.. GitHub STOP HELPING ICE

2

@Rs的解决方案非常出色，这只是64位变体，表已经计算好了...

static inline unsigned char bit_offset(unsigned long long self) {
    static const unsigned char mapping[64] = {
        [0]=0,   [1]=1,   [2]=2,   [4]=3,   [8]=4,   [17]=5,  [34]=6,  [5]=7,
        [11]=8,  [23]=9,  [47]=10, [31]=11, [63]=12, [62]=13, [61]=14, [59]=15,
        [55]=16, [46]=17, [29]=18, [58]=19, [53]=20, [43]=21, [22]=22, [44]=23,
        [24]=24, [49]=25, [35]=26, [7]=27,  [15]=28, [30]=29, [60]=30, [57]=31,
        [51]=32, [38]=33, [12]=34, [25]=35, [50]=36, [36]=37, [9]=38,  [18]=39,
        [37]=40, [10]=41, [21]=42, [42]=43, [20]=44, [41]=45, [19]=46, [39]=47,
        [14]=48, [28]=49, [56]=50, [48]=51, [33]=52, [3]=53,  [6]=54,  [13]=55,
        [27]=56, [54]=57, [45]=58, [26]=59, [52]=60, [40]=61, [16]=62, [32]=63
    };
    return mapping[((self & -self) * 0x022FDD63CC95386DULL) >> 58];
}

我使用提供的模板构建了这个表格。

>>> ', '.join('[{0}]={1}'.format(((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58, bit) for bit in xrange(64))
'[0]=0, [1]=1, [2]=2, [4]=3, [8]=4, [17]=5, [34]=6, [5]=7, [11]=8, [23]=9, [47]=10, [31]=11, [63]=12, [62]=13, [61]=14, [59]=15, [55]=16, [46]=17, [29]=18, [58]=19, [53]=20, [43]=21, [22]=22, [44]=23, [24]=24, [49]=25, [35]=26, [7]=27, [15]=28, [30]=29, [60]=30, [57]=31, [51]=32, [38]=33, [12]=34, [25]=35, [50]=36, [36]=37, [9]=38, [18]=39, [37]=40, [10]=41, [21]=42, [42]=43, [20]=44, [41]=45, [19]=46, [39]=47, [14]=48, [28]=49, [56]=50, [48]=51, [33]=52, [3]=53, [6]=54, [13]=55, [27]=56, [54]=57, [45]=58, [26]=59, [52]=60, [40]=61, [16]=62, [32]=63'

如果编译器报错：

>>> ', '.join(map(str, {((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58: bit for bit in xrange(64)}.values()))
'0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12'

^^^^ 假设我们对已排序的键进行迭代，但未来可能不是这种情况...

unsigned char bit_offset(unsigned long long self) {
    static const unsigned char table[64] = {
        0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48,
        28, 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49,
        18, 29, 11, 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43,
        21, 23, 58, 17, 10, 51, 25, 36, 32, 60, 20, 57, 16, 50,
        31, 19, 15, 30, 14, 13, 12
    };
    return table[((self & -self) * 0x022FDD63CC95386DULL) >> 58];
}

简单测试：

>>> table = {((2**bit * 0x022fdd63cc95386d) % 2**64) >> 58: bit for bit in xrange(64)}.values()
>>> assert all(i == table[(2**i * 0x022fdd63cc95386d % 2**64) >> 58] for i in xrange(64))

- Samy Vilar

1

除了使用汇编语言或编译器特定的扩展来查找第一个/最后一个设置的位之外，最快的算法是二分查找。首先检查前32位中是否有任何位被设置。如果是这样，请检查前16位是否有任何位被设置。如果是这样，请检查前8位是否有任何位被设置。以此类推。您可以在搜索的每个叶子节点上直接返回一个奇素数，或者它可以返回一个位索引，您可以将其用作奇素数表中的数组索引。

下面是一个循环实现二分查找的示例，如果被认为是最佳选择，编译器肯定可以展开它：

uint32_t mask=0xffffffff;
int pos=0, shift=32, i;
for (i=6; i; i--) {
    if (!(val&mask)) {
        val>>=shift;
        pos+=shift;
    }
    shift>>=1;
    mask>>=shift;
}

val 被假定为 uint64_t，但为了优化 32 位机器的性能，你应该特殊处理第一个检查，然后使用 32 位 val 变量执行循环。

- R.. GitHub STOP HELPING ICE

1

调用在glibc中找到的GNU POSIX扩展函数ffsll。如果该函数不存在，则回退到__builtin_ffsll。两个函数都返回设置的第一个位的索引+1，或零。使用Visual-C++，您可以使用_BitScanForward64。

- Matt Joiner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- R.. GitHub STOP HELPING ICE · Accepted Answer

最终一个最优解决方案。如果输入保证只有一个非零位，请参见本节末尾的操作: 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 序列是什么并使用 Google 之外，我不能因此获得任何功劳。 ;-)

关于它的工作原理还有一些额外的说明：

魔术数字是一个 B(2,6) 的 De Bruijn 序列。它具有以下特性：如果您查看一个6位连续的窗口，可以通过适当旋转该数字来获得该窗口中的任何六位值，并且每个可能的六位值都是通过恰好一个旋转获得的。

我们将要考虑的窗口固定为顶部的6个二进制位位置，并选择一个在前6位为0的 De Bruijn 序列。这使我们永远不必处理二进制旋转，只需要进行移位，因为0会自然地进入底部位（而且在上述顶部6位的窗口中，我们永远不可能查看超过从底部查看的5位）。

现在，该函数的输入值是2的幂。因此，将 De Bruijn 序列乘以输入值执行log2（value）位的位移操作。我们现在在顶部的6位中有一个数字，它唯一地确定了我们移动的位数，并且可以将其用作索引进入表格来获取实际位移的长度。

只要您愿意实现乘法，就可以对任意大或小的整数使用相同的方法，您只需找到其中 k 为位数的 B(2,k) De Bruijn 序列。我提供的上面的国际象棋 wiki 链接提供了从1到6的值的 De Bruijn 序列，而某些快速的 Googling 显示了一些生成它们的最优算法的论文。