Reverse int within the 32-bit signed integer range: \$[−2^{31}, 2^{31} − 1]\$ Optimized

Question

LeetCode Problem

Reverse digits of a 32-bit signed integer. When the reversed integer overflows return 0.

Feedback

Optimized from beta code in the original question here. Based on this LeetCode problem.. I'm trying to come up with a good approach that just math operations to iterate a serious of digits using division, almost treating the int like a stack popping using modulus, and pushing using multiplication.

#include <cassert>
#include <climits>
#include <cmath>
#include <iostream>

class Solution 
{
    public:
        int reverse(int i) {

            if(i > INT_MAX || i < INT_MIN) {
                return 0;
            }                            
            int sign = 1;
            if(i < 0) { 
                sign = -1;
                i = i*sign;
            }

            int reversed = 0;
            int pop = 0;

            while(i > 0) {      
                pop = i % 10;
                reversed = reversed*10 + pop;
                i /= 10;
            }                                

            std::cout << reversed << '\n';

            return reversed*sign;
        }
};

int main()
{
    Solution s;    

    assert(s.reverse(1) == 1);
    assert(s.reverse(0) == 0);
    assert(s.reverse(123) == 321);
    assert(s.reverse(120) == 21);
    assert(s.reverse(-123) == -321);
    assert(s.reverse(1207) == 7021);    
    assert(s.reverse(1534236469) == 0);
    assert(s.reverse(-2147483412) == -2143847412);
}

Answer 1

To prevent overflow, you need to check if reversed*10+pop > INT_MAX. But in order to avoid actually overflowing while checking, rearrange the equation to reversed > (INT_MAX-pop)/10;

Actually, I think you should check against -INT_MIN. Which brings up another point. You could use int64_t for reversed. This both ensures it can hold -INT_MIN before fixing the sign, and lets you do the bounds test only once at the end, instead of at each intermediate step.

I would initialize sign with the correct value: int sign = (i<0)?-1:1; i*=sign; . pop can be loop local and doesn't need the 0 initialization.

You should multiply reversed by sign before printing it.

Answer 2

Unused header

We use nothing from <cmath>, so it need not be included.

This should be a function, not a class

Putting all code into a class suggests you have a background in Java or similar.

In C++, we can (and should) use ordinary functions for operations that are mathematically functions. In this case, we have a pure function: it has no state, and should always give the same result for any given input.

If it's part of your program requirements that it must provide this (unhelpfully-named) class, then comment that. I'd recommend that you still write a plain function, and simply provide an adapter to conform to the requirements:

int reverse_decimal_digits(int i);

class Solution 
{
    public:
        int reverse(int i) { return reverse_decimal_digits(i); }
}

Choice of data type

If we're processing a 32-bit integer, then we should be using std::int32_t. Plain int isn't necessarily large enough (it can be any size from 16 bits upwards).

Incorrect test

Given int i, then i > INT_MAX || i < INT_MIN is false by definition. The requirement you quote is (my emphasis):

When the reversed integer overflows, return 0.

Not all integers have a negative

Beware of overflow here:

        if(i < 0) { 
            sign = -1;
            i = i*sign;
        }

On 2s-complement systems, -1 * INT_MIN is undefined.

It turns out that we don't need this step, as in modern C++, the % operator can be used predictably with negative numbers to our advantage (see my modified code, below).

Don't do I/O from a pure function

I guess this is some leftover debugging that should have been removed:

        std::cout << reversed << '\n';

Additional tests

It's good that you've included some unit tests - I wish more people would do that!

Do think about which values to test. Your choice agrees with mine somewhat, but diverges later:

• 0, 1 and -1 for the three simplest cases.
• positive and negative two-digit numbers (e.g. 12 and -23).
• smallest and largest allowable input (INT32_MIN and INT32_MAX).
• smallest and largest allowable result, and the first overflow in each direction in first and last digits (±1463847412, ±1463847413, ±1563847412).

Don't be tempted to over-test. Tests need to be maintained, too, so try to limit the tests to those that exercise the limits within the implementation.

Minor improvements

The scope of pop can be reduced to within the loop. And perhaps a better name would be digit?

noexcept and constexpr

Can we annotate the function with noexcept and constexpr?

Future

Should the number base be hard-coded to 10? Perhaps there's a use for a reverser that works in arbitrary bases. Certainly, base-16 is convenient for testing.

---

Modified code

I've used GoogleTest rather than plain C assert(), so as to get better messages when a test fails, but any testing method is fine.

#include <cstdint>

constexpr std::int32_t
reverse_digits(std::int32_t i, int base = 10) noexcept
{
    std::int32_t reversed = 0;
    const bool negative = i < 0;

    while (negative ? i <= -base : i >= base) {
        auto const digit = i % base; // negative if i < 0
        reversed = reversed * base + digit;
        i /= base;
    }

    // final digit may cause overflow
    const bool overflow =
        negative
        ? (reversed < (INT32_MIN - i) / base)
        : (reversed > (INT32_MAX - i) / base);
    if (overflow) {
        return 0;
    }

    return reversed * base + i;
}

#include <gtest/gtest.h>

TEST(Reverse, decimal)
{
    EXPECT_EQ(0, reverse_digits(0));
    EXPECT_EQ(1, reverse_digits(1));
    EXPECT_EQ(-1, reverse_digits(-1));

    EXPECT_EQ(21, reverse_digits(12));
    EXPECT_EQ(-32, reverse_digits(-23));

    EXPECT_EQ(0, reverse_digits(INT32_MIN));
    EXPECT_EQ(0, reverse_digits(INT32_MAX));

    EXPECT_EQ(2147483641, reverse_digits(1463847412));
    EXPECT_EQ(0, reverse_digits(1463847413));
    EXPECT_EQ(0, reverse_digits(1563847412));

    EXPECT_EQ(-2147483641, reverse_digits(-1463847412));
    EXPECT_EQ(0, reverse_digits(-1463847413));
    EXPECT_EQ(0, reverse_digits(-1563847412));
}

TEST(Reverse, hexadecimal)
{
    EXPECT_EQ(0x7ffffff7, reverse_digits(0x7ffffff7, 16));
    EXPECT_EQ(0, reverse_digits(0x10000008, 16));

    EXPECT_EQ(-0x7ffffff7, reverse_digits(-0x7ffffff7, 16));
    EXPECT_EQ(0, reverse_digits(-0x10000008, 16));
}