How to write log base(2) in c/c++

Question

Is there any way to write log(base 2) function?

The C language has 2 built in function -->>

1.log which is base e.

2.log10 base 10;

But I need log function of base 2.How to calculate this.

Answer 1

Simple math:

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

where y can be anything, which for standard log functions is either 10 or e.

Answer 2

C99 has log2 (as well as log2f and log2l for float and long double).

Answer 3

If you're looking for an integral result, you can just determine the highest bit set in the value and return its position.

Answer 4

#define M_LOG2E 1.44269504088896340736 // log2(e)

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

(multiplication may be faster than division)

Answer 5

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

Answer 6

If you want to make it fast, you could use a lookup table like in Bit Twiddling Hacks (integer log2 only).

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];

In addition you should take a look at your compilers builtin methods like _BitScanReverse which could be faster because it may entirely computed in hardware.

Take also a look at possible duplicate How to do an integer log2() in C++?

Answer 7

As stated on http://en.wikipedia.org/wiki/Logarithm:

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

Which means that:

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

Answer 8

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

Basically the same as tomlogic's.

Answer 9

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

Answer 10

You have to include math.h (C) or cmath (C++) Of course keep on mind that you have to follow the maths that we know...only numbers>0.

Example:

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

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

Answer 11

I needed to have more precision that just the position of the most significant bit, and the microcontroller I was using had no math library. I found that just using a linear approximation between 2^n values for positive integer value arguments worked well. Here is the code:

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));
}

In my main program, I needed to calculate N * log2(N) / 2 with an integer result:

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

and all 16 bit values were never off by more than 2%

Answer 12

All the above answers are correct. This answer of mine below can be helpful if someone needs it. I have seen this requirement in many questions which we are solving using C.

log2 (x) = logy (x) / logy (2)

However, if you are using C language and you want the result in integer, you can use the following:

int result = (int)(ceil(log(x) / log(2)));

Hope this helps.

Answer 13

Consult your basic mathematics course, log n / log 2. It doesn't matter whether you choose log or log10in this case, dividing by the log of the new base does the trick.

Answer 14

Improved version of what Ustaman Sangat did

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

    return val;
}