在接下来的内容中,包括程序,我假设double
由 IEEE 754 64 位二进制浮点数表示。这是最有可能的情况,但 C++ 标准不保证。
您可以在恒定时间内对某个范围内的双精度数进行计数,因为您可以通过从结尾减去开头并调整该范围是开放还是闭合来在恒定时间内对某个范围内的无符号整数进行计数。
有限非负范围内的双精度数具有形成连续整数序列的位模式。例如,范围 [1.0,2.0] 为范围 [0x3ff0_0000_0000_0000, 0x4000_0000_0000_0000] 中的每个整数包含一个双精度值。
双精度数的有限非正范围的行为方式相同,只是无符号位模式的值随着双精度数变得更负而增加。
如果您的范围同时包含正数和负数,请将其分割为零,以便您处理一个非负范围和另一个非正范围。
当您想要准确计数时,大多数复杂情况都会出现。在这种情况下,您需要调整范围是开放的还是封闭的,并且只计算一次零。
就您的目的而言,几亿分之一或二分之一的误差可能并不重要。
这是一个演示这个想法的简单程序。它几乎没有接受过错误检查,因此使用时需要您自担风险。
#include <iostream>
#include <cmath>
using namespace std;
uint64_t count(double start, double end);
void testit(uint64_t expected, double start, double end) {
cout << hex << "Should be " << expected << ": " << count(start, end)
<< endl;
}
double increment(double data, int count) {
int i;
for (i = 0; i < count; i++) {
data = nextafter(data, INFINITY);
}
return data;
}
double decrement(double data, int count) {
int i;
for (i = 0; i < count; i++) {
data = nextafter(data, -INFINITY);
}
return data;
}
int main() {
testit((uint64_t) 1 << 52, 1.0, 2.0);
testit(5, 3.0, increment(3.0, 5));
testit(2, decrement(0, 1), increment(0, 1));
testit((uint64_t) 1 << 52, -2.0, -1.0);
testit(1, -0.0, increment(0, 1));
testit(10, decrement(0,10), -0.0);
return 0;
}
// Return the bit pattern representing a double as
// a 64-bit unsigned integer.
uint64_t toInteger(double data) {
return *reinterpret_cast<uint64_t *>(&data);
}
// Count the doubles in a range, assuming double
// is IEEE 754 64-bit binary.
// Counts [start,end), including start but excluding end
uint64_t count(double start, double end) {
if (!(isfinite(start) && isfinite(end) && start <= end)) {
// Insert real error handling here
cerr << "error" << endl;
return 0;
}
if (start < 0) {
if (end < 0) {
return count(fabs(end), fabs(start));
} else if (end == 0) {
return count(0, fabs(start));
} else {
return count(start, 0) + count(0, end);
}
}
if (start == -0.0) {
start = 0.0;
}
return toInteger(end) - toInteger(start);
}