找出数字范围内的2个范围的幂？(在C中)

Question

如它是否落在2 ^ 3 - 2 ^ 4,2 ^ 4 - 2 ^ 5等内.返回的数字将是EXPONENT本身(减去偏移量).

如何尽可能快速有效地完成这项工作？这个函数将在一个非常依赖于速度的程序中被调用.这是我当前的代码,但它使用for循环效率太低.

static inline size_t getIndex(size_t numOfBytes)
{
    int i = 3;
    for (; i < 32; i++) 
    {
        if (numOfBytes < (1 << i)) 
            return i - OFFSET;
    }
    return (NUM_OF_BUCKETS - 1);
}

非常感谢你!

Answer 1

你所知道的只是log ₂(n),据我所知.

如果您的目标体系结构具有可以执行此操作的指令,则可能值得作弊并使用一些内联汇编.有关硬件支持的大量讨论和信息,请参阅维基百科关于"查找第一组"的条目.

Answer 2

一种方法是找到设置为1的最高位.我试图考虑这是否有效,因为在最坏的情况下你仍然需要进行n次检查.

也许你可以做一个二进制搜索样式,你检查它是否大于2 ^ 16,如果是,检查它是否大于2 ^ 24(假设这里是32位),如果没有,那么检查它是否大于2 ^ 20等等......这将是log(n)检查,但我不确定比特检查与完整int比较的效率.

可以获得一些perf数据.