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

Question

我需要拿一个size_t volume并计算这个结果size_t:

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

如果这个结果会溢出,size_t那么next应该为零.问题当然是volume * 8 + 3溢出,而整个结果适合于size_t.

目前我正在拆分最后4位volume并分别执行乘法,加法和除法.我的问题是:如果没有比这更大的类型,我能做得比目前为止做得更好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*音量<音量,所以你可以返回

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

这肯定比返回0更好.