在C语言中进行位溢出检查

Question

我正在尝试编写两个函数，以仅使用！~ | & ^ +检查/防止C中的溢出，但无法实现。第一个函数是fitsB(int x, int n)，用于检查特定的二进制补码/有符号整数是否适合使用某个位数：其中x是整数，n是要使用的位数。还有一个函数overflowInt(int x, int y)，用于检查两个整数相加时是否会发生溢出。如果它们是无符号整数，我可以做到，但负数会使事情变得更加困难。有人知道如何解决吗？

此外，没有强制转换，整数始终为32位。

- Gekctek

---

你忘记提出问题了。 - David Schwartz

Answer 1

/* 
 * addOK - Determine if can compute x+y without overflow
 *   Example: addOK(0x80000000,0x80000000) = 0,
 *            addOK(0x80000000,0x70000000) = 1, 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
 int addOK(int x, int y) {
  // Find the sign bit in each word
  //if a and b have different signs, you cannot get overflow.
  //if they are the same, check that a is different from c and b is different from c, 
  // if they are the same, then there was no overflow.
  int z=x+y;
  int a=x>>31;
  int b=y>>31;
  int c=z>>31;
  return !!(a^b)|(!(a^c)&!(b^c));
}

- Eric

---

这对你管用吗？ - Eric

sizeof(int)*8-1 对我来说比 31 更加清晰。 - ivan_pozdeev

这样做确实更加简洁，我使用了31，只是因为我们已经将int定义为始终为32位，并且我避免使用在我创建此函数时定义的“合法操作”之外的所有函数和方法，当时我正在上课。 - Eric

你使用有符号溢出的结果，这显然是未定义行为。 - Pod

Answer 2

如果 x < 2^(n-1)，那么 x 就可以适应 n 位。

溢出问题需要更多信息。如果将两个 int 分配给 long（或 double），它们就不会溢出。

- Adam Shiemke

---

没有强制类型转换，只有32位整数。 - Gekctek

Answer 3

使用上述示例（Adam Shiemke），您可以找到最大（正）值和最小值（负）以获取n位数的范围。 2^(n-1)（来自Adam的示例）和减去n位中可以表示的最大/正数的一个，即最大值/正数。对于最小值，取反2^(n-1)以获得最小值x => -（2^(n-1));（请注意，最小范围的符号是> =而不是>）。例如，对于n = 4位，2^(4-1) - 1 = 2^3 -1 = 7，因此x <= 7且x> = -8 =（-（2^(4-1))。

这假定初始输入不会溢出32位数量（希望在该条件下发生错误），并且您使用的位数少于32位（因为您正在为负范围添加1，如果您有32位，则会溢出，请参见下面的说明）。

为了确定加法是否会溢出，如果您拥有最大值，则 x + y <= 最大值。通过使用代数，我们可以得到 y <= 最大值 - x。然后，您可以比较传入的 y 值，如果它不满足条件，则加法会溢出。例如，如果 x 是最大值，则 y <= 0，因此 y 必须小于或等于零，否则加法将溢出。

- Glenn