C:找到一个值所属的bin索引

Question

我有区间呈指数增长的区间。

Bin 0 -> [0 <= x <= 10] (interval = 10)
Bin 1 -> [11 <= x <= 30] (interval = 20)
Bin 2 -> [31 <= x <= 70] (interval = 40)
Bin 3 -> [71 <= x <= 150] (interval = 80)
Bin 4 -> [151 <= x <= 310] (interval = 160)

...等等。

bin 的数量和第一个间隔是先验已知的(在本例中分别为 5 和 10)。 x 最低可能值为 0。

我目前做的是一个标准的for循环，每次乘以2，然后如果value在范围内则返回bin的索引。

有没有更聪明的方法来做到这一点？

Answer 1

根据 Weather Vane 的建议，

bin = floor( log2 (        (value + 9) / 10   ))

还有:

bin = floor( log2 ( floor( (value + 9) / 10 ) ))

C中的整数除法(i1/i2)等于trunc(i1/i2)(向零截断)，相当于非负整数的floor(i1/i2)，所以不需要实现内层。

floor(log2(i)) 可以非常有效地实现。查看accepted answer here用于快速的 32 位和 64 位整数实现。

代码如下(int 为 32 位时有效)。 OnlineGDB

#include <stdio.h>

const unsigned int tab32[32] = {
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7,
    19, 27, 23,  6, 26,  5,  4, 31};

unsigned int log2_32(unsigned int value)
{
    value |= value >>  1;
    value |= value >>  2;
    value |= value >>  4;
    value |= value >>  8;
    value |= value >> 16;
    return tab32[(value * 0x07C4ACDD) >> 27];
}

int main()
{
    unsigned int value = 151;

    unsigned int bin = 0;
    if (value > 0)
        bin = log2_32( (value + 9) / 10 );

    printf("value: %u, bin: %u", value, bin);

    return 0;
}