Как написать базу данных (2) в c/С++

Есть ли способ записать функцию log (base 2)?

Язык C имеет 2 встроенных функции → >

1. log, который является базой e.

2. log10 base 10;

Но мне нужна лог-функция базы 2. Как рассчитать это.

Ответ 1

Простая математика:

log ₂ (x) = log _y (x)/log _y (2)

где y может быть любым, что для стандартных логарифмических функций равно либо 10, либо e.

Ответ 2

Если вы ищете интегральный результат, вы можете просто определить самый старший бит, установленный в значении, и вернуть его позицию.

Ответ 3

C99 имеет log2 (а также log2f и log2l для float и long double).

Ответ 4

#define M_LOG2E 1.44269504088896340736 // log2(e)

inline long double log2(const long double x){
    return log(x) * M_LOG2E;
}

(умножение может быть быстрее, чем деление)

Ответ 5

log2(int n) = 31 - __builtin_clz(n)

Ответ 6

Как указано на http://en.wikipedia.org/wiki/Logarithm:

logb(x) = logk(x) / logk(b)

Это означает, что:

log2(x) = log10(x) / log10(2)

Ответ 7

Если вы хотите сделать это быстро, вы можете использовать таблицу поиска, например, в Bit Twiddling Hacks (только для целого log2).

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[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
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

Кроме того, вы должны взглянуть на свои компиляторы, встроенные методы, такие как _BitScanReverse, которые могли быть быстрее, потому что они могут полностью вычисляться на аппаратном уровне.

Взгляните также на возможный дубликат Как сделать целое число log2() в С++?

Ответ 8

log2(x) = log10(x) / log10(2)

Ответ 9

uint16_t log2(uint32_t n) {//but truncated
     if (n==0) throw ...
     uint16_t logValue = -1;
     while (n) {//
         logValue++;
         n >>= 1;
     }
     return logValue;
 }

В основном то же самое, что tomlogic.

Ответ 10

Вы должны включить math.h(C) или cmath (С++) Конечно, имейте в виду, что вы должны следовать математике, которую мы знаем... только цифры > 0.

Пример:

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    cout<<log2(number);
}

Ответ 11

Мне нужно было иметь более высокую точность, чем только позиция самого значимого бита, а микроконтроллер, который я использовал, не имел математической библиотеки. Я обнаружил, что просто использование линейного приближения между значениями 2 ^ n для аргументов положительного целочисленного значения хорошо работало. Вот код:

uint16_t approx_log_base_2_N_times_256(uint16_t n)
{
    uint16_t msb_only = 0x8000;
    uint16_t exp = 15;

    if (n == 0)
        return (-1);
    while ((n & msb_only) == 0) {
        msb_only >>= 1;
        exp--;
    }

    return (((uint16_t)((((uint32_t) (n ^ msb_only)) << 8) / msb_only)) | (exp << 8));
}

В моей основной программе мне нужно было вычислить N * log2 (N)/2 с целым результатом:

temp = (((uint32_t) N) * approx_log_base_2_N_times_256)/512;

и все 16-битные значения никогда не отключались более чем на 2%

Ответ 12

Обратитесь к основному курсу математики, log n / log 2. Неважно, выбираете ли вы log или log10 в этом случае деление на log новой базы делает трюк.

Ответ 13

Улучшенная версия того, что сделал Устаман Сангат

static inline uint64_t
log2(uint64_t n)
{
    uint64_t val;
    for (val = 0; n > 1; val++, n >>= 1);

    return val;
}