Search code examples
c++floating-accuracylogarithm

How to do an integer log2() in C++?

In the C++ standard libraries I found only a floating point log method. Now I use log to find the level of an index in a binary tree ( floor(2log(index)) ).

Code (C++):

int targetlevel = int(log(index)/log(2));

I am afraid that for some of the edge elements (the elements with value 2^n) log will return n-1.999999999999 instead of n.0. Is this fear correct? How can I modify my statement so that it always will return a correct answer?

Solution

  • You can use this method instead:

    int targetlevel = 0;
while (index >>= 1) ++targetlevel;

    Note: this will modify index. If you need it unchanged, create another temporary int.

    The corner case is when index is 0. You probably should check it separately and throw an exception or return an error if index == 0.