logo标签列表

在一个二进制数中找到第一个设置的位

c++bit-manipulation
12

我需要从右往左在一个二进制数中找到第一个被设置的位； 我想出了这个解决方案：

int cnt=0;
while (number& 1 ==0)
{
    cnt++;
    number>>=1;
}

有没有更好的方法？一些巧妙的位操作技巧吗？

这将会找到从右到左的第一个设置位。你想要哪一个？ - Chowlett
我纠正了问题，谢谢！ - user3283017
我目前没有时间将此转化为答案，但您可以使用位操作技巧中的这些来计算右侧连续零位数（因此是第一个设置的位）。 - Hasturkun
“更好”是指哪方面？可读性/可维护性、代码大小、二进制大小、性能方面？关于性能，您是否有关于预期输入的额外信息（例如概率分布）？ - Hulk
小心聪明才智的诱惑，许多伟大的思想都因此而失落。 - molbdnilo
5个回答
11

处理器可能直接有指令来找到它：

Windows/MSVC:

GCC:

这些通常直接映射到本机硬件指令。因此，它们比其他方法更快。

但是由于没有C/C++的功能，它们只能通过编译器内置函数访问。

您可以手动执行以下方式：

n & (n - 1) 是一种去除最右侧设置位的技巧。

因此，n - (n & n - 1) 将返回一个只有最右侧设置位的数字。

然后对结果进行 'log2' 运算即可得到解决方案：此链接可能会有所帮助

或者您可以使用所有 1 << k 的 switch case 语句来获得解决方案。

switch (n - (n & n - 1)) {
    case 0: ...
    case 1 << 0: return 0;
    case 1 << 1: return 1;
    ...
}
你的回答比neverhoodboy的回答更清晰，但基本上是相同的。你知道switch语句在机器代码级别上是如何评估的吗？它可能会变得与原始解决方案一样快甚至更慢（必须改进）。 - Ronald
@Ronald：我最初发布这个答案是为了解释neverhoodboy的回答。我发现在SO上有一些重复，现在我会尝试找到更好的手动技巧。 - Jarod42
1
我对你的回答感到非常满意，因为我不知道“n & (n - 1)”这个技巧。无论如何，最快的可移植方式可能是先逐字节进行测试，一旦发现有命中，就测试该字节是否设置了位。这将把操作次数从（平均）32 *（if + add + shift）减少到2 * if + 4 *（if + add + shift）。因此，有效地提高了近8倍的因素。 - Ronald
5

Bit Twiddling Hacks提供了一系列出色的位操作技巧，并附有性能/优化讨论。对于您的问题（来自该网站），您可以使用乘法和查找策略：

unsigned int c = number;  // your input number
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[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 = MultiplyDeBruijnBitPosition[((uint32_t)((c & -c) * 0x077CB531U)) >> 27];
1
假设是32位整数，这就是正确的答案。 - Xarn
1
@Xarn 另一个假设是使用二进制补码表示法？ - neverhoodboy
4
如果你想让它更快，位扫描指令（bsf，bsr）或位操作技巧是目标所在。 编辑： 使用switch-case表来提高性能的想法只是不成熟的。
@Ronald number 的第一个设置位将是 t 的唯一设置位，因此您只需要在 switch 中使用 32 或 64 个情况。 - neverhoodboy
1
个人而言，我不建议用晦涩难懂的计算和32或64路开关来替换一个习惯性可读的循环，除非它a）有充分的文档支持，并且b）已被证明对性能有实质性和必要的影响。 - molbdnilo
1
@Ronald 如果你真的想让它快速，那么位扫描指令（bsf，bsr）就是目标。 - neverhoodboy
2
为什么这么复杂？你可以直接使用 number & -number，对吧？或者是有一些晦涩的基于标准的反对意见吗？ - harold
@Ronald 我意识到对于这个问题，switch-case并不是一个好的选择。使用bitscan指令或bittwiddle hack会更好。当然，原帖中的方法也不错（当然要修复错误）。 - neverhoodboy
显示剩余4条评论
0

你的代码

int cnt=0;
   while (number& 1 ==0)
   {
       cnt++;
       number>>=1;
   }

有一个错误。例如，如果数字等于0，则循环将无限执行。

我会按照以下方式重写它

int cnt = 0;
if ( number ) while ( !( number & ( 1 << cnt++ ) ) );

在这种情况下，如果数字不等于0，则设置位的位置（cnt）将从1开始计数。否则，该位置将等于0。
0

我不确定被接受的答案是否正确。我刚刚测试了朴素循环和(num & -num)解决方案。它们的速度都是一样的。朴素循环代码更少。我使用以下方式构建：

来自MinGW的gcc 4.7.2，在Win 7上 gcc test.c -o test.exe -std=c99 -Wall -O2

这是我的代码（它可能有一些边角情况的错误，但我认为时间大致上是有效的）。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_NUMS 65536


int find_first_bits(unsigned nums[NUM_NUMS])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < 10000; j++) {
        for (int i = 0; i < NUM_NUMS; i++) {
            switch (nums[i] & -nums[i]) {
                case (1<<0): total += 1; break;
                case (1<<1): total += 2; break;
                case (1<<2): total += 3; break;
                case (1<<3): total += 4; break;
                case (1<<4): total += 5; break;
                case (1<<5): total += 6; break;
                case (1<<6): total += 7; break;
                case (1<<7): total += 8; break;
                case (1<<8): total += 9; break;
                case (1<<9): total += 10; break;
                case (1<<10): total += 11; break;
                case (1<<11): total += 12; break;
                case (1<<12): total += 13; break;
                case (1<<13): total += 14; break;
                case (1<<14): total += 15; break;
                case (1<<15): total += 16; break;
                case (1<<16): total += 17; break;
                case (1<<17): total += 18; break;
                case (1<<18): total += 19; break;
                case (1<<19): total += 20; break;
                case (1<<20): total += 21; break;
                case (1<<21): total += 22; break;
                case (1<<22): total += 23; break;
                case (1<<23): total += 24; break;
                case (1<<24): total += 25; break;
                case (1<<25): total += 26; break;
                case (1<<26): total += 27; break;
                case (1<<27): total += 28; break;
                case (1<<28): total += 29; break;
                case (1<<29): total += 30; break;
                case (1<<30): total += 31; break;
                case (1<<31): total += 32; break;
            }
        }
    }

    return total;
}


int find_first_bits2(unsigned nums[NUM_NUMS])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < 10000; j++) {
        for (int i = 0; i < NUM_NUMS; i++) {
            unsigned mask = 1;
            for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
                if (nums[i] & mask) {
                    total += cnt;
                    break;
                }
            }
        }
    }

    return total;
}


int main() {
    // Create some random data to test
    unsigned nums[NUM_NUMS];
    for (int i = 0; i < NUM_NUMS; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits(nums);
    end_time = clock();
    printf("Time = %.5f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits2(nums);
    end_time = clock();
    printf("Time = %.5f, result = %d\n", (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}
感谢您采取测试行动。我在我的帖子下面的评论里意识到了问题。实际上，我正在考虑删除我的答案，以免混淆任何人...... - neverhoodboy
你能否为大家最喜欢的位操作集合中的解决方案添加测试？http://graphics.stanford.edu/~seander/bithacks.html（请参见下面herohuyongtao的答案） - Xarn
@Xam：我今晚会做的。我现在正在工作 :-( - Andrew Bainbridge
DeBruijn乘法比朴素循环快60％，每个处理的数字大约需要11个周期。 - Andrew Bainbridge
比DeBruijin方法快3倍的是Andrew Grant的查找表方法，来源于https://dev59.com/6HRA5IYBdhLWcg3w_DDF。 - Andrew Bainbridge
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接