c - c中的按位溢出检查

Question

我正在尝试编写两个函数来检查/防止 c 中的溢出（仅使用！~ | & ^ +）但无法获得它。第一个是某些二进制补码/有符号整数将适合一定数量的位：fitsB(int x, int n) 其中是 int，n 是要使用的位大小。还有一个函数将检查两个整数相加时是否不会溢出：overflowInt(int x, int y)。如果它们是无符号整数，我可以得到它，但负数只会让我更难。有谁知道怎么做？

也没有强制转换，整数总是 32 位

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));
}

Answer 2

如果 x < 2^(n-1)，x 将适合 n 位。

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

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 必须小于或等于 0，否则加法将溢出。