整数乘17/64向下取整的溢出处理（限指定位运算）

原代码的核心问题是直接计算(x<<4)+x时，当x的绝对值较大，会触发有符号整数溢出（C中属于未定义行为），导致计算结果错误。

解决方案 #

通过拆分计算逻辑，避免直接计算x*17的溢出：将x分解为64*q + r（q是x除以64的向下取整结果，r是0~63的余数），此时floor(x*17/64)可拆分为17*q + floor(17*r/64)，每一步计算都不会超出int范围。

修正后的代码 #

#include <stdio.h>

int mulfrac(int x) {
    int q = x >> 6;          // 等价于floor(x/64)，算术右移自动处理正负
    int mul_q = (q << 4) + q;// 计算q*17，无溢出风险
    int r = x & 63;          // 取x的低6位，得到余数r（0~63）
    int mul_r = (r << 4) + r;// 计算r*17，最大值为63*17=1071，无溢出
    int low = mul_r >> 6;    // 计算floor(17*r/64)，正数右移等价向下取整
    return mul_q + low;
}

int main() {
    int test_values[] = {0, 1, -1, 3, -3, 17, -17, 11, -11, 64, -64, 128, -128, 100, -100, 400, 15, -6, 1234523590, -10000000, -10};
    int n_tests = sizeof(test_values) / sizeof(test_values[0]);

    for (int i = 0; i < n_tests; i++) {
        int x = test_values[i];
        int result = mulfrac(x);
        printf("mul_17_div_64(%d) = %d\n", x, result);
    }

    return 0;
}

关键逻辑说明 #

1. 拆分计算：将x拆分为高位部分q和低位余数r，避免直接计算x*17的溢出。
2. 无溢出保证：
   • q是x右移6位的结果，其绝对值仅为原x的1/64，乘17后远小于int的最大值/最小值，不会溢出。
   • r的范围是0~63，乘17后最大值为1071，完全在int范围内。
3. 向下取整正确性：
   • 对负数x，算术右移x>>6直接得到floor(x/64)，符合需求。
   • 正数r乘17后右移6位，等价于向下取整除法。

测试验证 #

• 对于x=-10：计算得q=-1，mul_q=-17，r=54，mul_r=918，low=14，最终结果-17+14=-3，与floor(-170/64)=-3一致。
• 对于大正数x=1234523590：结果为327920328，与floor(1234523590*17/64)的计算结果一致。

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