WebGPU中基于32位操作实现uint64与uint32的除法问题

问题根源 #

你之前采用的16位拆分公式，在除数b大于65535时，中间步骤的余数*2^16 + 当前块会超出uint32的范围，触发无符号整数溢出，导致低32位商的计算结果错误；即使b≤65535，若余数传递和商拼接的逻辑不严谨，也会出现低32位结果偏差。

通用解决方案：逐位长除法 #

采用模拟手动长除法的逐位处理逻辑，全程基于uint32操作，无溢出风险，支持任意uint32类型的除数（包括大于65535的情况）。

核心逻辑 #

将64位被除数（拆分为high和low两个uint32）视为整体，从最高位（第63位）到最低位（第0位）逐位左移，每一步判断当前被除数的高32位是否大于等于除数：

• 若是，减去除数并将商的对应位设为1
• 若否，商的对应位设为0
• 逐步拼接得到商的高32位和低32位

WGSL代码实现 #

// 输入：uint64被除数的高32位high、低32位low，uint32除数b
// 输出：vec2u(商的高32位, 商的低32位)
fn div_u64_u32(high: u32, low: u32, b: u32) -> vec2u {
    var res_high: u32 = 0u;
    var res_low: u32 = 0u;
    // 临时存储被除数的当前状态，避免修改输入
    var curr_high: u32 = high;
    var curr_low: u32 = low;

    // 遍历64位的每一位，从最高位到最低位
    for (var i: u32 = 0u; i < 64u; i++) {
        // 被除数整体左移1位：高位左移，低位的最高位来自原高位的最低位，低位左移补0
        let carry = curr_high >> 31u; // 原高位的最高位，作为低位左移的进位
        curr_high = (curr_high << 1u) | (curr_low >> 31u);
        curr_low = curr_low << 1u;

        // 判断当前高位是否大于等于除数，计算商的当前位
        var bit: u32 = 0u;
        if (curr_high >= b) {
            curr_high -= b;
            bit = 1u;
        }

        // 商整体左移1位，将当前位补到商的最低位
        res_high = (res_high << 1u) | (res_low >> 31u);
        res_low = (res_low << 1u) | bit;
    }

    return vec2u(res_high, res_low);
}

补充说明 #

• 若需要同时获取余数，最后curr_high即为64位被除数除以b的余数（因为余数始终小于b，存储在uint32中足够）。
• 该方法的时间复杂度为O(64)，在WebGPU的Shader中执行效率足够，不会成为性能瓶颈。

原16位拆分方法的修正（仅适用于b≤65535） #

如果你的场景中除数b始终≤65535，可以修正原方法的余数传递逻辑，避免低32位错误：

fn div_u64_u32_small_b(high: u32, low: u32, b: u32) -> vec2u {
    const x = 0x10000u; // 2^16
    let A = high >> 16u;
    let B = high & 0xFFFFu;
    let C = low >> 16u;
    let D = low & 0xFFFFu;

    var rem: u32 = 0u;
    var res_high: u32 = 0u;
    var res_low: u32 = 0u;

    // 处理高32位的两段
    res_high = (rem * x + A) / b;
    rem = (rem * x + A) % b;
    res_high = (res_high << 16u) | ((rem * x + B) / b);
    rem = (rem * x + B) % b;

    // 处理低32位的两段
    res_low = (rem * x + C) / b;
    rem = (rem * x + C) % b;
    res_low = (res_low << 16u) | ((rem * x + D) / b);

    return vec2u(res_high, res_low);
}

修正点在于严格按顺序拼接商的每一段，确保每一步的余数正确传递到下一段计算。

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