C: Нахождение индекса корзины, которому принадлежит значение

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)

... и т. Д.

Количество бинов и первый интервал известны ранее (в данном случае это 5 и 10 соответственно). x минимально возможное значение равно 0.

То, что я сейчас делаю, это стандартный цикл for, который умножается на 2 каждый раз, а затем возвращает индекс бина, если value находится в пределах диапазона.

Есть ли более разумный способ сделать это?

Answer 1

Как предполагает Weather Vane,

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

также:

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

Целочисленное деление (i1 / i2) в C равно trunc (i1 / i2) (усечение в направленииноль), что эквивалентно floor (i1 / i2) для неотрицательных целых чисел, поэтому нет необходимости реализовывать внутренний floor.

floor (log2 (i)) может быть реализован довольно эффективно.См. принятый ответ здесь для быстрых 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;
}

Answer 2

Арифметика журнала - это круто, но вы также можете просто построить таблицу и использовать двоичный поиск, чтобы найти корзину.

int find_bin(unsigned x) {
 static unsigned bin_top[] = {
    10u, // 0
    30u, // 1
    70u, // 2
    150u, // 3
    310u, // 4
    630u, // 5
    1270u, // 6
    2550u, // 7
    5110u, // 8
    10230u, // 9
    20470u, // 10
    40950u, // 11
    81910u, // 12
    163830u, // 13
    327670u, // 14
    655350u, // 15
    1310710u, // 16
    2621430u, // 17
    5242870u, // 18
    10485750u, // 19
    20971510u, // 20
    41943030u, // 21
    83886070u, // 22
    167772150u, // 23
    335544310u, // 24
    671088630u, // 25
    1342177270u, // 26
    2684354550u, // 27
    4294967295u, // 28
  };
  int lo = 0, hi = 28;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (mid > 0 && x <= bin_top[mid - 1]) hi = mid - 1;
    else if (x > bin_top[mid]) lo = mid + 1;
    else return mid;
  }
  return lo;
}

Цикл никогда не будет выполняться более пяти итераций, поэтому он довольно быстрый.Контейнер 28 - это самое большое значение без знака, которое не является расчетным.