CODEWITHSUNDEEP
c++c
russell
russell

Reputation: 3766

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

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.

Upvotes: 120

Views: 288625

Answers (14)

Mazhar MIK
Mazhar MIK

Reputation: 1192

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.

Upvotes: 3

Rian Quinn
Rian Quinn

Reputation: 1996

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

Upvotes: 0

Matthew Flaschen
Matthew Flaschen

Reputation: 284927

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

Upvotes: 77

logicray
logicray

Reputation: 680

#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)

Upvotes: 45

David Reinagel
David Reinagel

Reputation: 21

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%

Upvotes: 2

bkausbk
bkausbk

Reputation: 2790

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++?

Upvotes: 9

w00t
w00t

Reputation: 321

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

Upvotes: 25

user2143904
user2143904

Reputation: 41

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

Upvotes: 2

Ustaman Sangat
Ustaman Sangat

Reputation: 1543

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.

Upvotes: 5

tomlogic
tomlogic

Reputation: 11694

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

Upvotes: 59

Adam Crume
Adam Crume

Reputation: 15844

Simple math:

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

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

Upvotes: 226

Patrick
Patrick

Reputation: 23629

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

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

Which means that:

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

Upvotes: 9

the_void
the_void

Reputation: 5538

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

Upvotes: 3

Pieter
Pieter

Reputation: 2912

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.

Upvotes: 0

Related Questions