coverflowbitsignedunderflow

Detecting signed integer multiplication overflow in C


I'm writing this code for more than 3 hours already..

I gave up about the overflow thing and tried to google and look it up on stackoverflow.

I did not find any solution besides the one that I wrote in my code as you can see in lines 27-28 (where it returns 0). But this condition also does not work.

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

The input that is not working due to overflow is:

1534236469

The error code on leetcode is

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)

Other than that, the code is working and every number (positive & negative numbers) is being successfully reversed.

I'll be glad to hear you out about a possible solution and also let me know what do you think about my code and the way I decided to complete this task, I know that's the most basic and naïve way to do it, but I'll be glad to know how could I improve it.

The task is:

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


Solution

  • You can do something like this.

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