How to write log base(2) in c/c++
C++CC++ Problem Overview
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.
C++ Solutions
Solution 1 - C++
Simple math:
log2 (x) = logy (x) / logy (2)
where y can be anything, which for standard log functions is either 10 or e.
Solution 2 - C++
C99 has log2
(as well as log2f
and log2l
for float and long double).
Solution 3 - C++
If you're looking for an integral result, you can just determine the highest bit set in the value and return its position.
Solution 4 - C++
#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)
Solution 5 - C++
log2(int n) = 31 - __builtin_clz(n)
Solution 6 - C++
As stated on http://en.wikipedia.org/wiki/Logarithm:
logb(x) = logk(x) / logk(b)
Which means that:
log2(x) = log10(x) / log10(2)
Solution 7 - C++
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 https://stackoverflow.com/questions/994593/how-to-do-an-integer-log2-in-c
Solution 8 - C++
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.
Solution 9 - C++
log2(x) = log10(x) / log10(2)
Solution 10 - C++
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);
}
Solution 11 - C++
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%
Solution 12 - C++
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.
Solution 13 - C++
Consult your basic mathematics course, log n / log 2
. It doesn't matter whether you choose log
or log10
in this case, dividing by the log
of the new base does the trick.
Solution 14 - C++
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;
}