Calculating bit_Delta(double p1, double p2) in C++

user_3508551 0
Viewed 76

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?

bit-manipulation c++
2 Answers

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.

user_36843430

The following idea is based on conversion of the double values to fixed-point arithmetic, comparing the integers with XOR and counting the equal most significant bits.

#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>(p2 * 0x80000000U);
    return std::countl_zero(i1 ^ i2);
}

It returns 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 unsigned long long int instead of unsigned int you could increase the precision to 53 (i.e. the precision of double numbers).

The function countl_zero - included with the bit header - was introduced in C++20.

user_131300480
Related