如何计算无符号64位整数的Q64.64定点二进制对数？附代码解析疑问

一、纯整数实现Q64.64分数部分计算（Rust） #

整数部分你已明确：用63 - x.leading_zeros()得到w（x为非零u64），核心是分数部分的迭代逼近，这里用二进制逐位确定法，全程无浮点数、无第三方库，依赖Rust的u128支持：

原理 #

将原数x归一化到[1,2)区间（对应Q64.64格式的[2^64, 2^65)），此时log2(x) = w + log2(f)，其中f是归一化后的数。我们需要计算log2(f)的64位二进制小数，通过迭代平方逐位确定每一位：

• 每次将当前f平方，若平方结果≥2（Q64.64对应≥2^128），则当前二进制位为1，将f除以2继续迭代；否则当前位为0，直接用平方结果继续迭代。
• 每轮迭代对应分数部分的一位，迭代64次即可得到完整的64位分数。

Rust代码实现 #

fn log2_q64_64(x: u64) -> u128 {
    assert!(x != 0, "log2(0) is undefined");
    
    // 计算整数部分w
    let w = 63 - x.leading_zeros() as u128;
    
    // 归一化到Q64.64格式的[2^64, 2^65)区间
    let mut f = (x as u128) << (64 - w as u32);
    
    let mut frac = 0u64;
    
    // 迭代64次确定每一位分数
    for i in 0..64 {
        let f_sq = f.checked_mul(f).expect("overflow"); // Q64.64平方后为Q128.128
        let threshold = 1u128 << 128;
        
        if f_sq >= threshold {
            // 当前位为1，记录到分数部分对应位置
            frac |= 1 << (63 - i);
            // 更新f为 (f² / 2) 的Q64.64格式
            f = (f_sq >> 64) >> 1;
        } else {
            // 当前位为0，更新f为f²的Q64.64格式
            f = f_sq >> 64;
        }
    }
    
    // 组合整数部分和分数部分，得到Q64.64结果
    (w << 64) | frac as u128
}

精度说明 #

该方法能达到64位分数精度，远超过你需要的5-6位，迭代过程仅涉及整数乘法和移位，效率极高。

二、Uniswap TickMath.sol log2代码解析 #

Uniswap的实现针对区块链环境做了gas优化，核心用多项式近似替代迭代，处理的是Q64.96格式的定点数，逻辑如下：

核心步骤 #

1. 整数部分计算：通过bitLength()确定输入的最高有效位，将输入归一化到[1<<96, 2<<96)区间（对应[1,2)的实数），得到整数部分w。
2. 小数部分近似：令d = f - 1<<96（f为归一化后的数，d是Q96格式的小数部分，范围[0, 1<<96)），利用log2(1+d) ≈ (d - d²/2 + d³/3) / ln2的三阶泰勒展开近似计算。
3. 组合结果：将整数部分w<<96与近似得到的小数部分相加，得到Q64.96格式的log2结果。

为什么用多项式近似？ #

区块链上的运算gas成本极高，迭代64次平方的gas开销远大于几次乘法和除法。三阶泰勒展开在[0,1)区间的误差足够小（满足Uniswap的tick计算需求），同时大幅降低运算成本。

关键细节 #

• INV_LN2：预计算的1/ln2的Q96格式定值（约1.442695），用于将自然对数转换为二进制对数。
• 定点数运算：所有计算均通过移位实现除法（如d*d/(2<<96)等价于(d*d) >> 97），避免浮点数操作。

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