检测 C 中的有符号整数乘法溢出

Question

我写这段代码已经 3 个多小时了..

我放弃了关于溢出的事情并尝试 google 并在 Whosebug 上查找它。

除了您在 lines 27-28（其中 returns 0）中看到的我在代码中编写的解决方案之外，我没有找到任何解决方案。但是这个条件也不行。

#include <stdio.h>

int reverse(int x) {
  int pos = 0;
  int reversed = 0;
  int numOfDigits = 0;
  int tenPower = 1;
  if (x < 0) {
    pos = -x;
  } else
    pos = x;
  while (pos > 0) {
    pos = (pos - (pos % 10)) / 10;
    numOfDigits++;
  }
  while (numOfDigits > 0) {
    for (int i = numOfDigits - 1; i > 0; i--) {
      if (numOfDigits == 1)
        tenPower = 1;
      else
        tenPower *= 10;
    }
//overflow check - does not work
    if (x % 10 != 0 && ((x % 10) * tenPower) / (x % 10) != tenPower)
      return 0;
    reversed += (x % 10) * tenPower;
    numOfDigits--;
    x = (x - (x % 10)) / 10;
    tenPower = 1;
  }
  if (x < 0)
    return -reversed;
  else
    return reversed;
}

int main() {
  int arr[5] = {-30, 120, 1501, 321, 0};
  for (int i = 0; i < 5; i++) {
    printf("Original number is: %d \n", arr[i]);
    printf("Reversed number is: %d \n", reverse(arr[i]));
  }
}

由于溢出而无法正常工作的输入是：

1534236469

leetcode上的错误码是

Line 25: Char 28: runtime error: signed integer overflow:

1000000000 * 9 cannot be represented in type 'int' [solution.c]

Line: if (x%10 != 0 &&((x%10)*tenPower) / (x%10) != tenPower)

除此之外，代码正在运行，每个数字（正数和负数）都被成功反转。

我很高兴听到您提出可能的解决方案，并让我知道您对我的代码的看法以及我决定完成此任务的方式，我知道这是最基本和天真的方式去做吧，但我很高兴知道如何改进它。

任务是：

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Examples:

Input: x = 123 Output: 321, Input: x=-120 Output = -21

Answer 1

您要检查溢出的主要内容是：

reversed += (x % 10) * tenPower;

那么你想知道的是这是否属实：

((x % 10) * tenPower) > INT_MAX

或者这是真的：

(reversed + (x % 10) * tenPower) > INT_MAX

当然，由于溢出，这些在代码中永远不可能成立，但我们可以重新排列术语：

if ((x % 10) != 0 && (tenPower > INT_MAX / (x % 10)) || 
                      (((x % 10) * tenPower) > INT_MAX - reversed))
    return 0;

Answer 2

你可以这样做。

int reverse(int n) {
    // 1st overflow checking...
    // Check if the absolute value is greater than INT32_MAX.
    // I converted "int" to "long" to get correct overflow value.
    if (n < 0 && (long) n * -1l > INT32_MAX) {
        return 0;
    }
    
    int res = 0;
    // Convert to absolute value.
    int tmp = n < 0 ? n * -1 : n;
    
    while (tmp > 0) {
        // Get the right most digit and add it to the current result.
        res += tmp % 10;
        // Remove the right most digit.
        tmp /= 10;
        
        // "tmp" still has remaining numbers.
        if (tmp > 0) {
            // 2nd overflow checking...
            // Check if reversed value will be greater than INT32_MAX when appending 0 to right most.
            // I converted "int" to "long" to get correct overflow value.
            if ((long) res * 10l > INT32_MAX) {
                return 0;
            }
            
            // Append 0 to right most value of result.
            // If result is equal to 0, do not append 0.
            res *= res == 0 ? 1 : 10;
        }
    }
    
    // Return result.
    // If original value is negative, return negative result value..
    return n < 0 ? res * -1 : res;
}

Answer 3

OP 的代码在多处int 溢出

  if (x < 0) { pos = -x; }
  ...
  (x % 10) * tenPower
  ....
  reversed += (x % 10) * tenPower;
  ...
  if (x < 0) return -reversed;

一个简单的溢出预测试涉及INT_MAX/INT_MIN

  if (x < 0) { 
    if (x < -INT_MAX) { puts("Overflow"); return 0; }
    pos = -x;
  }

  // x is >= 0 here, tenPower >= 1
  int digit = x % 10;
  if (digit > INT_MAX/tenPower)     { puts("Overflow"); return 0; }
  int digit10 = digit * tenPower;
  if (reversed > INT_MAX - digit10) { puts("Overflow"); return 0; }
  reversed += digit10;

或使用单机全系列tests.

// Return 1 on overflow
int is_undefined_mult1(int a, int b) {
  if (a > 0) {
    if (b > 0) {
      return a > INT_MAX / b;       // a positive, b positive
    }
    return b < INT_MIN / a;         // a positive, b not positive
  }
  if (b > 0) {
    return a < INT_MIN / b;         // a not positive, b positive
  }
  return a != 0 && b < INT_MAX / a; // a not positive, b not positive
}

  int digit = x % 10;
  if (is_undefined_mult1(digit, tenPower))  { puts("Overflow"); return 0; }
  int digit10 = digit * tenPower;
  if (is_undefined_add1(reversed, digit10)) { puts("Overflow"); return 0; }
  reversed += digit10;

Answer 4

您可以使用 bit_length() 检查整数大小

if digit.bit_length() >= 32:
        return 0
    else:
        return reversed

检测 C 中的有符号整数乘法溢出

Detecting signed integer multiplication overflow in C

c

signed

overflow

bit

underflow