询问std::ceil(int_x/std::log2(int_y))是否始终准确及精确计算方法

一、std::ceil(int_x / std::log2(int_y))能否保证精确结果？ #

不能保证，确实会因浮点精度问题导致结果偏差1。

原因在于：

• 当y不是2的整数次幂时，log2(y)是无理数，无法用二进制浮点数（比如double）精确表示，只能存储近似值。
• 用这个近似值计算int_x / std::log2(int_y)时，结果会和真实值存在微小误差。如果真实值刚好略大于某个整数N，但浮点计算结果略小于N，std::ceil后会得到N，而正确结果应该是N+1；反之，若真实值略小于N+1但浮点计算结果略大于，std::ceil会得到N+1，正确结果应为N。

举个典型场景：假设y=7（log2(7)≈2.80735，无理数），x=2807354923，真实值x/log2(y)≈1000000000.356，正确的ceil结果是1000000001。但由于std::log2(7)的浮点近似值略大于真实值，计算出的x/std::log2(y)可能接近999999999.999999，std::ceil后得到1000000000，偏差1。

二、精确计算ceil(x * 8 / log2(y))的最简方法 #

可以通过数学转换+整数二分查找完全避免浮点误差，步骤如下：

核心转换 #

原表达式等价于找最小的整数k，满足：

k * log2(y) ≥ x * 8

两边取2的幂（由于2的幂是单调递增函数，不等号方向不变），得到：

y^k ≥ 2^(8x)

问题转化为：找到满足y^k ≥ 2^(8x)的最小正整数k。

实现思路 #

1. 计算目标值：T = 2^(8x)，可以用位运算1ULL << (8*x)（注意若8x超过64位，需用多精度整数库处理）。
2. 二分查找：
   • 初始范围：low=1，high=8*x（当y=2时，k=8x是精确解，作为上限足够）。
   • 每次取中间值mid，用带溢出判断的快速幂计算y^mid，判断是否≥T：
     • 若y^mid ≥ T，说明mid可能是候选解，尝试缩小上限high=mid；
     • 若y^mid < T，说明需要更大的k，调整下限low=mid+1。
3. 最终low即为所求的k。

示例代码（C++） #

#include <cstdint>

bool power_ge(int y, int k, uint64_t target) {
    uint64_t result = 1;
    uint64_t base = static_cast<uint64_t>(y);
    while (k > 0) {
        if (k % 2 == 1) {
            // 提前判断溢出：result * base 会超过 target
            if (result > target / base) {
                return true;
            }
            result *= base;
            if (result >= target) {
                return true;
            }
        }
        k /= 2;
        if (k > 0) {
            // 提前判断base平方溢出
            if (base > target / base) {
                return true;
            }
            base *= base;
        }
    }
    return result >= target;
}

int ceil_8x_over_log2y(int x, int y) {
    if (y == 1) {
        // log2(1)=0，原表达式无意义，根据需求处理错误
        return -1;
    }
    uint64_t target = 1ULL << (8 * x);
    int low = 1;
    int high = 8 * x;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (power_ge(y, mid, target)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

优势 #

• 完全基于整数运算，无浮点精度损失；
• 快速幂+二分查找的时间复杂度为O(log(8x) * logk)，效率较高；
• 边界情况（如y=2，此时log2(y)=1，k=8x）能直接得到精确解。

内容的提问来源于stack exchange，提问作者Chris_F