I am working on a fixed-point platform (floating-point arithmetic not supported).

I represent any rational number `q` as the floor value of `q * (1 << precision)`.

I need an efficient method for calculating log base 2 of `x`, where `1 < x < 2`.

Here is what I've done so far:

```
uint64_t Log2(uint64_t x, uint8_t precision)
{
    uint64 res = 0;

    uint64 one = (uint64_t)1 << precision;
    uint64 two = (uint64_t)2 << precision;

    for (uint8_t i = precision; i > 0 ; i--)
    {
        x = (x * x) / one; // now 1 < x < 4
        if (x >= two)
        {
            x >>= 1; // now 1 < x < 2
            res += (uint64_t)1 << (i - 1);
        }
    }

    return res;
}

```

This works well, however, it takes a toll on the overall performance of my program, which requires executing this for a large amount of input values.

For all it matters, the `precision` used is 31, but this may change so I need to keep it as a variable.

Are there any optimizations that I can apply here?

I was thinking of something in the form of "multiply first, sum up last".

But that would imply calculating `x ^ (2 ^ precision)`, which would very quickly overflow.

Update
------

I have previously tried to get rid of the branch, but it just made things worse:

```
for (uint8_t i = precision; i > 0 ; i--)
{
    x = (x * x) / one; // now 1 < x < 4
    uint64_t n = x / two;
    x >>= n; // now 1 < x < 2
    res += n << (i - 1);
}

return res;

```