Reputation: 75
Reverse of a Integer with integer overflow condition
long long reverse(long long x) {
long long reversednum=0;
int sign=1;
if(x<0)
sign=-1;
x=abs(x);
while(x)
{
reversednum=reversednum*10;
reversednum=reversednum+(x%10);
x=x/10;
}
return (reversednum<INT_MAX || reversednum>INT_MIN)?reversednum*sign:0;
}
Most of my test cases got satisfied except for this 1534236469 which returns the output 1056389759. I have seen many suggestions and changed it to long long. But still produces the same result. Hope some would help me out. Thanks in advance!! The input is assumed to be a 32-bit signed integer. My function should return 0 when the reversed integer overflows
Upvotes: 0
Views: 1581
Answers (4)
Reputation: 12668
The problem with your question is that you are assuming that the problem is in the sign bit (and that you cannot overflow with the significant bits), and it isn't there, you get errors well before approaching the sign bit. After analysing your code, there is a final unsigned 32 bit integer overflow in the last multiplication by 10 (you multiply by 10, not by 2, so you can get up to four new bits in each multiplication, making it easier for an overflow), even if you do unsigned arithmetic (which is recommended so you don't need to play with the signs)
Just modifiying a little your code to use unsigned arithmetic, and issuing some traces in the reverse function to this version of your program:
#include <stdio.h>
#include <stdlib.h>
unsigned reverse(unsigned x, unsigned base)
{
unsigned reversednum=0;
while(x) {
unsigned digit = x % base;
reversednum *= base;
reversednum += digit;
x /= base;
printf("reverse: digit=%u, reversednum=%u, x=%u, base=%u\n",
digit, reversednum, x, base);
}
return reversednum;
}
int main()
{
char buffer[100];
while ( fgets(buffer, sizeof buffer, stdin) ) {
unsigned x = (unsigned) atol(buffer);
printf("reverse(%u) => %u\n", x, reverse(x, 10));
} /* while */
} /* main */
Execution with your input gives:
$ reversed
23
reverse: digit=3, reversednum=3, x=2, base=10
reverse: digit=2, reversednum=32, x=0, base=10
reverse(23) => 32
1534236469
reverse: digit=9, reversednum=9, x=153423646, base=10
reverse: digit=6, reversednum=96, x=15342364, base=10
reverse: digit=4, reversednum=964, x=1534236, base=10
reverse: digit=6, reversednum=9646, x=153423, base=10
reverse: digit=3, reversednum=96463, x=15342, base=10
reverse: digit=2, reversednum=964632, x=1534, base=10
reverse: digit=4, reversednum=9646324, x=153, base=10
reverse: digit=3, reversednum=96463243, x=15, base=10
reverse: digit=5, reversednum=964632435, x=1, base=10 <-- after multipliying
by base, unsigned
overflows here to
9,646,324,350 -
2*4,294,967,296 ==
1,056,389,758
reverse: digit=1, reversednum=1056389759, x=0, base=10
reverse(1534236469) => 1056389759
The main problem with your code is that the last digit in your number (a ten digit number) can be 0..9 and the first digit in your ten digit number cannot be more than 4 (if it is 4, then the second cannot be more than 2... or an overflow ocurs, giving a number that is larger than the maximum possible value for an unsigned) For example, all numbers greater than 1,000,000,000 finished in 5 or more, will overflow, from the set of numbers that finish in 4, all the ones that finish in 2 or more will overflow, from the numbers that finish in 24, the ones that
finish in 924 that have a previous digit greater than 4, all will overflow, ... and so until forming the number MAX_UINT in the base you are doing the calculations.
This happens also for signed numbers, so you have to limit the domain of your function to not overflow. As all ten digit numbers with a last digit of 5 will overflow, i'd suggest a maximum value of 1,000,000,005, for the first number that overflows. For different bases, you'll have different limits, so you must be careful (I shouldn't allow numbers that greater or equal base^(floor(log(MAX_UINT)/log(base))) ==> 1,000,000,000, as you'll begin to get windows of numbers that overflow, interspersed with numbers that don't --- in the case of 32bit unsigned the first number that fails is 1,000,000,005, while for signed numbers it is 1,000,000,003)
For 64 bit unsigneds, the limit should be at 1.0E19 ( == 10^((int)(log((double)MAX_ULONG_LONG)/log(10.0)))), as 10,000,000,000,000,000,002 is the first failing number. For signeds, the limit should be at 1.0E18, as 1,000,000,000,000,000,039should be the first number to fail.
JUST TO COMPLETE
to consider a function that works properly with a set of 32bit integers, you should make an assertion like the one you do, but instead of using INT_MAX or INT_MIN, you have to use actual bounding limits for your number. Something like
#include <stdint.h>
#include <assert.h>
int32_t reverse(int32_t x)
{
assert(x > -1000000000 && x < 1000000000);
int32_t reversednum = 0;
while(x) {
int digit = x % 10;
reversednum *= 10;
reversednum += digit;
x /= 10;
} /* while */
return reversednum;
} /* reverse */
would allow to even disable the range check at runtime for production code. base has been fixed to 10, as this was your function, and the assert(3) limits depend of the election of the numbering base.
Upvotes: 0
Reputation: 3825
I am sure you must be using %ld inside printf...Use %lld! Simple mistake :)
Analysis of what was happening:
When you entered 1534236469 result should be 9646324351 which was correctly produced by the function(yes it was!).
In binary, 9646324351 is written as 00000010 00111110 11110111 00111010 01111111 . Now your compiler allocates 4 bytes for long and 8 bytes for long long. So when you print long (where it should have been long long) the compiler will simply take the first 4 bytes from the binary and discard the rest. This means that your compiler simply takes 00111110 11110111 00111010 01111111 which is equivalent to 1056389759 in decimal. Hence the output... So it means that your function and logic is correct(phewwww....!!!!) but you made a silly mistake.
Upvotes: 1
Reputation: 5525
It is quite complicated to check the number before you reverse it, so:
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>
#include <limits.h>
long long reverse(long long x)
{
long long reversednum = 0;
// just in case
// please be aware that the minimum size for "int" is 16-bit!
// you might think about changing it to an actual number if you
// really need 32-bit
long long int_max = INT_MAX;
long long int_min = INT_MIN;
int sign = 1;
// abs() would have been wrong for "long long", it should have been "llabs()"
// also: you already checked if x is negative, no need for "abs()" here
if (x < 0){
sign = -1;
x = -x;
}
while (x) {
reversednum = reversednum * 10;
reversednum = reversednum + (x % 10);
x = x / 10;
}
// you want "reversednum" to be in the range {int_min < reversednum < int_max}
// hence the need to check both limits
return (reversednum < int_max
&& reversednum > int_min) ? reversednum * sign : 0;
}
int main(int argc, char **argv)
{
long long x;
if (argc != 2) {
fprintf(stderr, "Usage: %s integer\n", argv[0]);
exit(EXIT_FAILURE);
}
errno = 0;
x = strtoll(argv[1], NULL, 10);
if ((errno == ERANGE && (x == LLONG_MAX || x == LLONG_MIN))
|| (errno != 0 && x == 0)) {
fprintf(stderr, "Input %s caused an error in converting: %s\n", argv[1],
strerror(errno));
exit(EXIT_FAILURE);
}
printf("IN : %lld\n", x);
x = reverse(x);
printf("OUT : %lld\n", x);
exit(EXIT_SUCCESS);
}
As said in the comments but worth to repeat here, too: the limits int_* have a guaranteed minimum of only 16-bits (ISO/IEC 9899:2011 5.2.4.2.1)!
Upvotes: 1
Reputation: 122
You're using INT_MAX and INT_MIN, when you should probably be using LLONG_MAX and LLONG_MIN
long long reverse(long long x) {
long long reversednum = 0;
int sign = 1;
if (x<0)
sign = -1;
x = abs(x);
while (x)
{
reversednum = reversednum * 10;
reversednum = reversednum + (x % 10);
x = x / 10;
}
return (reversednum<LLONG_MAX || reversednum>LLONG_MIN) ? reversednum*sign :
0;
}
int main(){
long long int i;
scanf_s("%lld", &i);
printf("%lld",reverse(i));
scanf_s("%d", &i);
}
It has been tested on the values 1232 and your given value that shows bad results(1534236469).
Upvotes: -1