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.

Crabby

For eyeball computations, the base 2 logarithm is close to equal to the base 10 logarithm plus the natural logarithm. Obviously it's better to write a more accurate (and faster) version in a program. – Advanced

For integers, you could loop on right bitshift, and stop when reached 0. The loop count is an approximation of the log – Quinquennium

Fast computing of log2 for 64-bit integers, What's the quickest way to compute log2 of an integer in C#? – Oder

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.

Gibber

Answer 2

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

Baggs

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.

Hibbert

There is also a nice bit-twiddling method for this (taken from Java's Integer.highestOneBit(int) method): i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); – Saunderson

...or while (i >>= 1) { ++l; } – Logion

@Saunderson That would work assuming integer is 32 bit wide, no ? For 64 bit it would have an extra i>>32 . But since Java has only 32-bit ints, it is fine. For C/C++ it needs to be considered. – Permit

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)

Becerra

Just wanted to clarify - using the log conversion rules + the fact that log_2(e) = 1/log_e(2) --> we get the result – Cislunar

Answer 5

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

Bencher

Answer 6

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

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

Which means that:

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

Hathor

Note that you can precompute log10(2) to increase performance. – Capper

@Johannes: I doubt the compiler will pre-compute log10(2). The compiler doesn't know that log10 will return the same value every time. For all the compiler knows, log10(2) could return different values on successive calls. – Sign

@abelenky: Ok, I take that back. Since the compiler never sees the source to the log() implementation it won't do it. My bad. – Saunderson

@abelenky: Since log10() is a function defined in the C standard, the compiler is free to treat it "specially", including precomputing the result, which I believe was @Johannes' suggestion? – Bouton

+1 @caf. I've never tried with log, but I've seen such optimizations with sqrt many times. – Hixson

@CarlNorum: I've just checked, and gcc 4.7 at least replaces log10(2) with a constant. – Bouton

@abelenky: The compiler can know that if it can verify that the function follows certain scoping rules (i.e., uses only parameters and local variables, and only calls functions which follow the same rules). Compilers are pretty smart these days, I'd be surprised if it was not replaced. – Accordion

even if it didn't do it at compile time, make it a const static and you take the hit just once. – Venom

Answer 7

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

Coprolalia

Why the multiplication and table lookup at the end? Couldn't you just do (v+1) which would round up to the next power of two? And then, you could shift right by one to round down to the next power of 2. – Nisi

@SafayetAhmed Please describe how you want to find the log2 of a number with that method. I don't know an easier way to get that value. Beside using the arithmetic above with lookup table, one can use an iterative/recursive algorithm or using dedicated/builtin hardware to do the calculation. – Coprolalia

Say the bits of a 32 bit variable v are numbered 0 (LSB) through N (MSB). Say the most significant set bit of v is n. Would it be correct to say that n represents floor( log2(v) )? Aren't you interested in just finding n given v? – Nisi

I realized that what I described would just give you the nearest lowest power of 2 and not the actual logarithm. The multiplication and table lookup are for going from the power of two to the logarithm. You are shifting the number 0x07C4ACDD left by some amount. The amount you shift left will depend on the power of two. The number is such, that any consecutive sequence of 5 bits is unique. (0000 0111 1100 0100 0110 1100 1101 1101) gives you the sequences (00000) (00001) ... (11101). Depending on how far left you shift, you get one of these 5-bit patterns. Then table lookup. Very nice. – Nisi

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.

Insanitary

There are a couple of things wrong with this solution, but in general, this is nice if you want to avoid floating points. You are relying on overflow for this to work since you are initializing an unsigned integer with -1. This could be fixed by initializing it to 0 and then returning the value - 1, assuming you check for the 0 case, which you do. The other issue is you are relying on the loop stopping when n == 0, whic you should state explicitly. Other than that, this is great if you want to avoid floating points. – Chuu

Answer 9

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

Minorca

Upvote for simplicity, clarity, and providing code based on the OP's given information. – Nubianubian

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

Allopatric

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%

Cassette

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.

Stalingrad

This will create a wrong answer when x is a power of 2, that +1 is for forcibly rounding up, which is not needed if x is 2, 4, 8, 16, 32, 64 etc - ceil might be better than floor – Tildatilde

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.

Symptomatic

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

Chuu