If we consider the binary representation of numbers, we could find that the result of is actually related to the position of the first appearance of in the binary bits. Let’s see some example below:
For any positive integer , we have the following relationship:
#include <iostream>
using std::cout, std::endl;
unsigned log2LowerBound(unsigned long long number)
{
// records the MSB where the first 1 occurred in binary representation
unsigned firstPosition = 0;
// record the current index
unsigned currentIdx = 0;
while (number > 0)
{
if (number & 1)
{
firstPosition = currentIdx;
}
number >>= 1;
++currentIdx;
}
return firstPosition;
}
int main()
{
for (int i = 0; i < 17; ++i)
{
cout << "log2 lower bound of " << i << " is: " << log2LowerBound(i) << endl;
}
return 0;
}