Alex Rivera | Logout

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

Asked 2010-06-17T19:25:51.193
119

Is there any way to write log2() function?

The C language has 2 built in functions

  1. log which is base e.
  2. log10 base 10;

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

c++ c logarithm
Edit
Report

1 Answer

9

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

answered 2013-08-05T06:12:31.383

Your Answer