2

可能重复：
用于计数位或找到最右边|最左边的有效位运算

我写了一个搜索算法。为了优化它，我想用a32bit int来标记是否可以使用数字0~31。也就是说，如果我有一个 state State，我可以使用以下方法轻松获取所有可能的数字：

x = State & -State
State -= x

但实际上，我需要知道 1 在哪里x（注意二进制形式只有 1 x）？例如，如果x = 0000 0100，我想知道那是第三个。

我知道我可以通过使用for循环来做到这一点，但似乎会花费很多时间。

我想知道是否有使用按位运算的方法？并且会static_cast<int>(log2(x))花费很多时间吗？

谢谢你的帮助。

4

4 回答 4

3

许多 CPU 都有本机硬件指令，例如CTZ（“计数尾随零”）。GCC 通过内置函数 __builtin_ctz公开这一点；其他编译器应该有类似的设施。

于 2012-09-28T09:28:22.347 回答
3

似乎没有人提到明显的解决方案 - 使用一个巨大的开关来处理所有可能的 2 次方。

下面的代码实现了这一点，加上二进制搜索和除以二。

注意：这些函数期望输入是 2 的幂；如果不是，他们可能会胡说八道。

#include <inttypes.h>
#include <stdio.h>

int get_exp_switch (uint64_t x)
{
    switch (x) {
        case (uint64_t)1 << 0: return 0;
        case (uint64_t)1 << 1: return 1;
        case (uint64_t)1 << 2: return 2;
        case (uint64_t)1 << 3: return 3;
        case (uint64_t)1 << 4: return 4;
        case (uint64_t)1 << 5: return 5;
        case (uint64_t)1 << 6: return 6;
        case (uint64_t)1 << 7: return 7;
        case (uint64_t)1 << 8: return 8;
        case (uint64_t)1 << 9: return 9;
        case (uint64_t)1 << 10: return 10;
        case (uint64_t)1 << 11: return 11;
        case (uint64_t)1 << 12: return 12;
        case (uint64_t)1 << 13: return 13;
        case (uint64_t)1 << 14: return 14;
        case (uint64_t)1 << 15: return 15;
        case (uint64_t)1 << 16: return 16;
        case (uint64_t)1 << 17: return 17;
        case (uint64_t)1 << 18: return 18;
        case (uint64_t)1 << 19: return 19;
        case (uint64_t)1 << 20: return 20;
        case (uint64_t)1 << 21: return 21;
        case (uint64_t)1 << 22: return 22;
        case (uint64_t)1 << 23: return 23;
        case (uint64_t)1 << 24: return 24;
        case (uint64_t)1 << 25: return 25;
        case (uint64_t)1 << 26: return 26;
        case (uint64_t)1 << 27: return 27;
        case (uint64_t)1 << 28: return 28;
        case (uint64_t)1 << 29: return 29;
        case (uint64_t)1 << 30: return 30;
        case (uint64_t)1 << 31: return 31;
        case (uint64_t)1 << 32: return 32;
        case (uint64_t)1 << 33: return 33;
        case (uint64_t)1 << 34: return 34;
        case (uint64_t)1 << 35: return 35;
        case (uint64_t)1 << 36: return 36;
        case (uint64_t)1 << 37: return 37;
        case (uint64_t)1 << 38: return 38;
        case (uint64_t)1 << 39: return 39;
        case (uint64_t)1 << 40: return 40;
        case (uint64_t)1 << 41: return 41;
        case (uint64_t)1 << 42: return 42;
        case (uint64_t)1 << 43: return 43;
        case (uint64_t)1 << 44: return 44;
        case (uint64_t)1 << 45: return 45;
        case (uint64_t)1 << 46: return 46;
        case (uint64_t)1 << 47: return 47;
        case (uint64_t)1 << 48: return 48;
        case (uint64_t)1 << 49: return 49;
        case (uint64_t)1 << 50: return 50;
        case (uint64_t)1 << 51: return 51;
        case (uint64_t)1 << 52: return 52;
        case (uint64_t)1 << 53: return 53;
        case (uint64_t)1 << 54: return 54;
        case (uint64_t)1 << 55: return 55;
        case (uint64_t)1 << 56: return 56;
        case (uint64_t)1 << 57: return 57;
        case (uint64_t)1 << 58: return 58;
        case (uint64_t)1 << 59: return 59;
        case (uint64_t)1 << 60: return 60;
        case (uint64_t)1 << 61: return 61;
        case (uint64_t)1 << 62: return 62;
        case (uint64_t)1 << 63: return 63;
        default: return 0; // not allowed
    }
}

int get_exp_simple (uint64_t x)
{
    int i = -1;
    do {
        i++;
        x /= 2;
    } while (x > 0);
    return i;
}

int get_exp_binsearch (uint64_t x)
{
    int left = 63;
    int right = 0;

    while (left > right) {
        int middle = (left + right) / 2;
        uint64_t middle_value = (uint64_t)1 << middle;
        if (x < middle_value) {
            left = middle - 1;
        }
        else if (x > middle_value) {
            right = middle + 1;
        }
        else {
            return middle;
        }
    }

    return left;
}

int main ()
{
    uint64_t sum = 0;

    for (int j = 0; j < 100000; j++) {
        for (int i = 0; i < 64; i++) {
            uint64_t x = (uint64_t)1 << i;
            int l = get_exp_switch(x);
            //int l = get_exp_simple(x);
            //int l = get_exp_binsearch(x);
            sum += l;
            //printf("%" PRIu64 ": %d\n", x, l);
        }
    }

    printf("%" PRIu64 "\n", sum);

    return 0;
}

我的（64 位）系统上的基准测试结果clang -O2：

get_exp_switch: 0m0.103s
get_exp_simple: 0m0.196s
get_exp_binsearch: 0m0.158s

但是，请注意，当您使用较大的整数 (bignum) 时，二分查找方法将很快开始优于简单方法，并且 switch 方法的代码大小可能会变得无法接受。

于 2012-09-28T09:45:43.983 回答
1

如果您必须使用按位运算符，您可以使用此处的位扫描技巧，但是，大多数编译器都有用于查找第一个/最后一个设置位的内部函数，即 BitScanForward 和 BitScanReverse，这些函数在现代处理器上非常快，应该使用（从技术上讲，这些是按位运算，也就是说，它们对位进行运算，只是没有运算符形式）。

于 2012-09-28T09:16:42.853 回答
0

您可以进行 log(n) 搜索（伪 c 代码，没有尝试过但应该可以工作，n 等于位置）：

STATE = 0010 0000
int bits=8;

int n=1;
while(bits>1)
{
    bits >>=1;//right shift 1
    int upper = STATE>>bits; //get the upper half
    if(upper)
    {
        n+=bits;
        STATE>>=bits;
    }
    //else the "1" is on the right side
}

您还可以在预先创建的表中进行查找，即。执行上面的循环（因为 32 位表可能会占用太多空间）但在（例如）位 == 4 时停止并在 16 字节长的查找表中进行查找（您可以将该数字添加到'n'）。

于 2012-09-28T09:50:37.347 回答