Calculating bit_Delta(double p1, double p2) in C-CodePudding

I am interested in computing the function int bit_Delta(double p1, double p2) for two doubles in the range [0,1). The function returns the index where the two doubles deviate in binary after the dot.

For example, 1/2 = 0.10 in binary, and 3/4=0.11 in binary. So bit_delta(0.5, 0.75) should return 2 because their first digit (1) is the same, but the second is the first digit where they differ.

I've thought about calculating the mantissa and exponent separately for each double. If the exponents are different, I think I can do it, but if the exponents are the same, I don't know how to use the mantissa. Any ideas?

CodePudding user response：

One way would be to compare if both values are above 0.5 ==> both have the first bit set, else if both are below 0.5 ==> both have the first bit not set.

If both are above 0.5, subtract 0.5 and half the treshold, continue till you found the threshold, where the values are not both above or both below it.

#include <iostream>
int bit_delta(double a, double b)
{
    if (a == b) return -1;
    double treshold = 0.5;
    for (int digit = 1; digit < 20; digit  , treshold /= 2)
    {
        if (a < treshold && b < treshold)
        {
        }
        else if (a >= treshold && b >= treshold)
        {
            a -= treshold;
            b -= treshold;
        }
        else
            return digit;
    }
    return 20; //compare more than 20 digits does not make sense for a double
}

int main()
{
    std::cout << bit_delta(0.25, 0.75) << std::endl;
    std::cout << bit_delta(0.5, 0.75) << std::endl;
    std::cout << bit_delta(0.7632, 0.751) << std::endl;
}

This code returns 1 2 7.

CodePudding user response：

You can use

#include <bit>

int bit_delta(double p1, double p2)
{
    unsigned int i1 = static_cast<unsigned int>(p1 * 0x80000000U);
    unsigned int i2 = static_cast<unsigned int>(p1 * 0x80000000U);
    return std::countl_zero(i1 ^ i2);
}

It would return results between 1 .. 32.

With positive inputs p1 and p2 below 1. the MSB of i1 and i2 would always be zero, which is needed to get the counting right.

By using long long int you could increase the precision to 53.

countl_zero included in bit was introduced in C 20.