如何“融合”两个值不溢出？

问题描述 投票：3回答：3

考虑下面的函数：

// Return a blended value of x and y:
//   blend(100, 200, 1, 1) -> 150
//   blend(100, 200, 2, 1) -> 133
uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  uint32_t big_parts_x = parts_x;
  uint32_t big_parts_y = parts_y;
  return (uint8_t) ((big_parts_x * x + big_parts_y * y) /
                    (big_parts_x + big_parts_y));
}

有没有办法去接近相应的回报值，而不需要比uint8_t更大的任何分配？你可以通过执行两个部门打破它（四舍五入少）为增加两个uint16_t容易。你可以只用uint8_t办呢？

c algorithm integer-overflow
3个回答
4
投票

甲符合标准C实现是保证具有至少16位执行算术运算。

在C standard国科6.3.1.1p2：

以下可以在表达式中使用的任何地方可使用int或unsigned int：

  • 一个整型（比int或unsigned int其他），其整数转换等级的对象或表达是小于或等于int和unsigned int的秩。
  • 型_Bool，int，signed int，或unsigned int的位字段。

如果int可以表示原始类型的所有值（如由宽度的限制，对于一个位字段），该值被转换为int;否则，它被转换为一个unsigned int。这些被称为整数促销。所有其它类型在整数提升不会改变。

节E.1还指出，一个int必须能够支持范围为-32767至少值32767，以及unsigned int必须支持在至少范围为0〜65535的值。

由于uint8_t具有比int等级较低，前者总是被晋升为后者时，它是大多数运营商，包括+，-，*和/的主题。

鉴于这种情况，你可以放心地计算与以下略作修改的值：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
    return ((1u*parts_x*x) / (parts_x + parts_y)) + ((1u*parts_y*y) / (parts_x + parts_y));
}

表达式parts_x*x和parts_y*y将具有最大值的65025.这是太大对于一个16位int但不是一个16位的unsigned int，因此每个由1u迫使值相乘，以转换为unsigned int按照通常的算术转换在第6.3.1.8中指定：

整数提升在两个操作数执行。然后下面的规则应用到推动操作数：

  • 如果两个操作数具有相同的类型，则不需要进一步的转换。
  • 否则，如果两个操作数已签署整数类型或两者都具有的无符号整数类型，具有较小整数转换等级的类型的操作数转换为操作数的具有更大的秩的类型。
  • 否则，如果具有无符号整数类型的操作数的秩大于或等于另一个操作数的类型的秩，然后用带符号的整数类型的操作数被转换成无符号整数类型的操作数的类型。

还需要注意的是，我们通过总和分别将每个部分。如果我们增加了两个部分首先将前，分子可能会超过65535先做的划分，这会带来各subexpession回落到一个uint8_t的范围。然后，我们可以添加两个部分，这将又是一个uint8_t的范围。

所以上面的表达式是保证在编译器，符合标准C返回正确的确切答案。

1
投票

下面将结合没有任何额外拨款。 作品即使int/unsigned是16位。

return (uint8_t) ((1u*parts_x*x + 1u*parts_y*y) / (0u + parts_x + parts_y));
1
投票

有没有办法去接近相应的回报值，而不需要任何分配比uint8_t更大？

从理论上说，是的：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  return lookup_table[x][y][parts_x][parts_y];
}

在实践中，那将花费的RAM的查找表4吉布，所以它可能不是一个好主意。

除此之外，这取决于你所说的“亲密”是什么（有多大“可以接受最坏的情况下错误”即可），什么值的范围是有效的（特别是对parts_x和parts_y）。

例如（如果parts_x和parts_y具有从1至15的范围只）：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  uint8_t scaleX = (parts_x << 4) / (parts_x + parts_y);
  uint8_t scaleY = (parts_y << 4) / (parts_x + parts_y);

  return (x >> 4) * scaleX + (y >> 4) * scaleY;
}

在这种情况下，当然“接近”是指：

  • 共混物（100，200，1，1）= 6 * 8 + 12 * 8 = 144（未150）
  • 共混物（100，200，如图2所示，1）= 6 * 10 + 12×5 = 120（未133）

需要注意的是（一般）乘法“扩大”。我的意思是，如果a具有范围M位和b具有范围N位，然后a*b将有一系列M + N位。换句话说（使用全范围），以避免溢出uint8_t * uint8_t = uint16_t。司是显著恶化（例如，以避免精度损失，需要1/3无限比特），一些精度损失是无法避免，位在结果中的数量决定精度多少损失，和精度8位是“没有太多的” 。

另外请注意，我上面所示的简单的例子可以为某些情况下，通过增加额外的代码，这些情况得到改善。例如：

uint8_t blend(uint8_t x, uint8_t y, uint8_t parts_x, uint8_t parts_y) {
  if(parts_x < parts_y) {
     return blend(y, x, parts_y, parts_x);
  }
  // parts_x <= parts_y now

  if(parts_x == parts_y*2) {
      return 2*(x/3) + y/3;
  } else if(parts_x == parts_y*3) {
      return 3*(x/4) + y/4;
  } else if(parts_x == parts_y*4) {
      return 4*(x/5) + y/5;
  } else if(parts_x == parts_y*5) {
      return 5*(x/6) + y/6;
  } else if( (x > 16) && (y > 16) ){
      uint8_t scaleX = (parts_x << 4) / (parts_x + parts_y);
      uint8_t scaleY = (parts_y << 4) / (parts_x + parts_y);

      return (x * scaleX + y * scaleY) >> 4;
  } else {
      uint8_t scaleX = (parts_x << 4) / (parts_x + parts_y);
      uint8_t scaleY = (parts_y << 4) / (parts_x + parts_y);

      return (x >> 4) * scaleX + (y >> 4) * scaleY;
  }
}

当然，这是显著更容易和更快地使用的东西比uint8_t较大，所以...

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.