c - 使用C查找log2的优化方法

Question

我正在寻找一种有效的方法(最好使用少量位运算)，该方法返回左移计数或将方程解为:

find x for a given y where y=2^x

例如 (1 << 4) = 16 = 10000b。因此，如果给出 16，我该如何解决给定情况下左移量 4 的问题。另外，我不寻找涉及循环或日志方法的方法，例如:

unsigned int count_shift(unsigned int shifted)
{
    unsigned int count = 0;

    for (count = 0; shifted != 0x1; count++)
    {
        shifted /= 2;   
    }
    return count;
}

干杯!

Answer 1

如果保证该数字是2的幂，即y == 1 << x ，您可以使用 256 字节的查找表和四个查找来完成:

static unsigned char lookup[256] = {
    [0x01]=1, [0x02]=2, [0x04]=3, [0x08]=4, [0x10]=5, [0x20]=6, [0x40]=7, [0x80]=8
};

unsigned log2uint(unsigned y) {
    unsigned res = lookup[(y >>  0) & 0xFF];
    if (res) return res +  0 - 1;
    res = lookup[(y >>  8) & 0xFF];
    if (res) return res +  8 - 1;
    res = lookup[(y >> 16) & 0xFF];
    if (res) return res + 16 - 1;
    res = lookup[(y >> 24) & 0xFF];
    if (res) return res + 24 - 1;
    return 0;
}

Demo 1

如果您不介意供应商特定的功能，gcc 提供 __builtin_ctz返回尾随零的数量的函数，它与 y == 1 << x 时获得的返回值匹配(Demo 2)