Reverse 32bit integer

Chiheb Nexus picture Chiheb Nexus · Jun 16, 2017 · Viewed 19.4k times · Source

I'm trying to solve an exercie in leetcode.com which deals with signed 32bit integers.

The task is:

Return the inverse of a signed 32bit integer and return 0 if it overflows the 32bit signed integer's range.

In Wikipedia:

A 32-bit register can store 32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common representations, the range is 0 through 4,294,967,295 (2^32 − 1) for representation as an (unsigned) binary number, and −2,147,483,648 (−2^31) through 2,147,483,647 (2^31 − 1) for representation as two's complement.

So, if what i understood is correct i should test between the intervals 0 to (2^31)-1 and (-2^31) to 0 otherwise, return 0.

Here is my code:

def reverse_int(nums):
    a = str(nums)

    if 0 < nums <= (1 << 31)-1:
        return int(a[::-1])

    elif (-1 << 31) <= nums < 0:
        return -(int(a[:-len(a):-1]))
    else:
        return 0

Here is my problem: When i test my code on the website with:

nums = 1534236469 # Fail
nums = 1463847412 # Success
nums = 9000000    # Success

Why my current code fails with 1534236469 ? isn't 1534236469 in the range of 32 bit signed integers ? What i'm missing ?

Answer

void picture void · Jun 16, 2017

As mentioned in the comments you must first reverse and then check. However here's a different way of checking.

To check you can just & the result with the appropriate mask.

So in your case the limits are −2,147,483,648 and 2,147,483,647 the hex values of them are -0x80000000 and 0x7fffffff

Try this in the interpreter.

>>> 0x7fffffff
2147483647
>>> 2147483647 & 0x7fffffff   #within limit
2147483647

Values exceeding the limit, you can see some other value is displayed.

>>> 2147483648 & 0x7fffffff     #Exceeds limit
0
>>> 98989898989898 & 0x7fffffff  #Exceeds limit
1640235338

But when the value is within limit. The value is given as output.

>>> 1 & 0x7fffffff               #within limit
1
>>> 780 & 0x7fffffff
780

For negative values

 >>> -0x80000000     #Limit
-2147483648
>>> -2147483648 & -0x80000000
-2147483648

When the value is within the range. The limit is given as output.

>>> -2147483647 & -0x80000000
-2147483648
>>> -2 & -0x80000000          #within limit
-2147483648
>>> -2323 & -0x80000000
-2147483648

However if value is out of range you can see some other value is displayed.

>>> -2147483649 & -0x80000000
-4294967296
>>> -999999999999 & -0x80000000
-1000727379968

You can make use of this well and good to get what you want!

Here is a program that does what you want.

def reverse(x):
    str_x = str(x)
    if x<0:
        str_x = '-'+str_x[::-1][:-1]
        x = int(str_x)
    else:
        str_x = str_x[::-1]
        x = int(str_x)
    neg_limit= -0x80000000
    pos_limit= 0x7fffffff

    if(x<0):
        val=x&neg_limit
        if(val==neg_limit):
            return x
        else:
            return 0
    elif(x==0):
        return x
    else:
        val = x&pos_limit
        if(val==x):
            return x
        else:
            return 0

value = int(input("Enter value: "))
print(reverse(value))

The part below just reverses for both negative and positive values.

if x<0:
    str_x = '-'+str_x[::-1][:-1]
    x = int(str_x)
    print(x)
else:
    str_x = str_x[::-1]
    x = int(str_x)
    print(x)

Set the limits neg_limit= -0x80000000 and pos_limit= 0x7fffffff and check for them according to the explained logic.