c - 有没有更好的方法来计算 (n * 8 + 3)/5？

Question

我需要取一个 size_t 体积 并在 size_t 中计算这个结果:

size_t next = (volume * 8 + 3) / 5

如果此结果会溢出 size_t，则 next 应该为零。问题当然是 volume * 8 + 3 可能溢出，而整个结果适合 size_t。

目前我正在拆分volume的最后4位并分别执行乘法、加法和除法。我的问题是:如果没有大于 size_t 的类型，我能否做得比目前更好？

size_t next_volume(size_t volume) {
  // check if the numerator will overflow size_t
  if (volume > (SIZE_MAX - 3) / 8) {
    size_t lower, upper;

    // multiply lower 4 bits by 8 and add 3
    lower = ((volume & 0xF) * 8) + 3;
    // downshift the rest and multiply by 8
    upper = (volume >> 4) * 8;

    // divide upper remainder and lower by 5
    lower = ((upper % 5 << 4) + lower) / 5;

    // divide upper by 5
    upper = upper / 5;

    // ensure the sum will not overflow size_t
    if (upper + (lower >> 4) > SIZE_MAX >> 4)
      return 0;

    return (upper << 4) + lower;
  } else return (volume * 8 + 3) / 5;
}

该代码中可能存在一些错误。我还没有对它进行广泛的测试，但我相信所有的主要想法都在那里。

Answer 1

设 vol1 = volume % 5，vol2 = volume - vol1。 vol2 可以被 5 整除，因此在数学上是 (vol2 * 8)/5 = (vol2/5) * 8，所以你得到正确的结果为

size_t vol1 = volume % 5;
size_t vol2 = volume - vol1;
size_t result = (vol2 / 5) * 8 + (vol1 * 8 + 3) / 5

很明显，如果结果不适合 size_t，您将得到溢出，但如果计算中的任何地方都存在溢出则不会。因为你乘以 8/5，如果发生溢出，结果将约为 0.6 * volume < volume，所以你可以返回

return result < volume ? (size_t) -1 : result;

这肯定比返回 0 更好。