In this article, we will dive into various ways to reverse a number using integer reversal. We will begin by exploring the iterative approach, which breaks down numbers into individual digits and rebuilds them in reverse order. Next, we will discuss recursion as an alternative solution. We will also use a built-in function Math.Pow() for number reversal. Additionally, we will explore the two-pointer approach, where elements from opposite ends are swapped until they meet. Finally, we will examine the advantages of using the BigInteger class to handle large numbers.
Let’s start.
Create a Benchmark Baseline
Let’s set up our code environment to explore integer reversal techniques. We’ll utilize a console application and create separate methods for each reversal technique, each accepting an integer parameter num and returning the reversed integer reversedNumber.
But before we tackle different integer methods, we need to establish a baseline for string reversal. We’ll use it later to compare performance between integer and string reversal techniques.
Let’s create a method ReverseAsString() which accepts an integer parameter num and returns the reversed number:
public static int ReverseAsString(int num)
{
if (num == int.MaxValue || num == int.MinValue || num == 0)
{
return 0;
}
var isNegative = num < 0;
ReadOnlySpan<char> numChars = Math.Abs(num).ToString().AsSpan();
var length = numChars.Length;
Span<char> reversedChars = stackalloc char[length];
for (int i = 0; i < length; i++)
{
reversedChars[i] = numChars[length - i - 1];
}
if (int.TryParse(reversedChars, out int reversedNumber))
{
return isNegative ? -reversedNumber : reversedNumber;
}
else
{
return 0;
}
}
Here, we convert the num parameter into a character span reversedChars. Then we iterate through reversedChars and store each character in the reversed order. Finally, we convert this character array into an integer reversedNumber.
This approach provides a straightforward and efficient method for reversing integers using string manipulation techniques.
With the string-based reversal baseline done, let’s delve into reversing integers directly.
Reverse a Number by Digit Extraction and Reconstruction
This approach delves into the number, extracts each digit, and then places them in a temporary variable. The extracted digits are rearranged and reassembled to form the reversed number.
Let’s create a method ReverseUsingDigitExtractionAndReconstruction() to implement this approach:
public static int ReverseUsingDigitExtractionAndReconstruction(int num)
{
int maxValueDiv10 = int.MaxValue / 10;
int minValueDiv10 = int.MinValue / 10;
if (num == int.MaxValue || num == int.MinValue || num == 0)
{
return 0;
}
var reversedNumber = 0;
while (num != 0)
{
var remainder = num % 10;
if (reversedNumber > maxValueDiv10 || reversedNumber < minValueDiv10)
{
return 0;
}
reversedNumber = reversedNumber * 10 + remainder;
num /= 10;
}
return reversedNumber;
}
Our ReverseUsingDigitExtractionAndReconstruction() method reverses an integer by extracting and rebuilding its digits. To start, we initialize reversedNumber to zero. Inside our while loop, we extract the last digit of num, multiply the current reversedNumber by 10 to shift digits left, and add the extracted digit.
Finally, we divide num by 10 to remove the last digit. This loop repeats until all digits are processed, resulting in the reversed integer in reversedNumber.
Recursion to Reverse a Number
In recursion, a function calls itself within its definition, unlike traditional loops with counters. The recursion continues iteratively until the pre-defined base case is satisfied, triggering the unwinding of the call stack.
To understand this better, we use the same steps as ReverseUsingDigitExtractionAndReconstruction() method, but instead of a while loop, we use recursion.
Let’s declare a method ReverseUsingRecursion() with two parameters – an integer num and an optional reversedNumber which defaults to zero:
public static int ReverseUsingRecursion(int num, int reversedNumber = 0)
{
int maxValueDiv10 = int.MaxValue / 10;
int minValueDiv10 = int.MinValue / 10;
if (num == int.MaxValue || num == int.MinValue || num == 0)
{
return reversedNumber;
}
if (reversedNumber > maxValueDiv10 || reversedNumber < minValueDiv10)
{
return 0;
}
var remainder = num % 10;
reversedNumber = reversedNumber * 10 + remainder;
return ReverseUsingRecursion(num / 10, reversedNumber);
}
We extract the last digit of num and add it to a left-shifted reversedNumber (multiplied by 10) to build the reversed integer digit by digit. To process the remaining digits, we call ReverseUsingRecursion() again with the remaining number, num/10 and the updated reversedNumber. This chain of calls constructs the reversed number digit by digit. Finally, the last call returns the complete reversed number, propagating it back to the initial call for the final result.
Math.Pow
In .NET Math.Pow() is a built-in method in the Math class, that replaces repetitive multiplication with efficient exponentiation.
Let’s create a method ReverseUsingMathPow() that reverses integer num using Math.Pow():
public static int ReverseUsingMathPow(int num)
{
int maxValueDiv10 = int.MaxValue / 10;
var isNegative = num < 0;
num = isNegative ? -num : num;
if (num == int.MaxValue || num == int.MinValue || num == 0)
{
return 0;
}
int length = (int)Math.Floor(Math.Log10(num) + 1);
var reversedNumber = 0;
var powersOf10 = new int[10];
powersOf10[0] = 1;
for (int i = 1; i < 10; i++)
{
powersOf10[i] = powersOf10[i - 1] * 10;
}
for (int i = length - 1; i >= 0; i--)
{
var remainder = num % 10;
if ((remainder * powersOf10[i] / 10) >= maxValueDiv10)
{
return 0;
}
reversedNumber += remainder * powersOf10[i];
num /= 10;
}
return isNegative ? -reversedNumber : reversedNumber;
}
Within our while loop, we extract the rightmost digit remainder using num % 10. The remainder is then multiplied by the current power of 10 powerOf10 and added to the reversedNumber. Finally, we remove the processed digit from num and update the position value for the next iteration, continuing until all digits are reversed.
Here we use Math.Log10() to calculate the number of digits in num, however, it cannot process negative numbers. Therefore, to handle negative numbers during reversal, we convert them to positive ones before applying these techniques and then restore the original sign afterward.
Let’s transition from right-to-left digit extraction to a bidirectional approach to reverse a number.
Reverse a Number With Digit Swapping
This time, we can employ an iterative approach, traversing the digits of a number from both ends, gradually progressing toward the center.
Let’s create ReverseBySwappingDigits() to reverse number num and return the reversed version reversedNumber:
public static int ReverseBySwappingDigits(int num)
{
int maxValueDiv10 = int.MaxValue / 10;
if (num == int.MaxValue || num == int.MinValue || num == 0)
{
return 0;
}
var isNegative = num < 0;
num = isNegative ? -num : num;
int reversedNumber = 0;
int totalNumOfDigits = (int)Math.Floor(Math.Log10(num)) + 1;
int[] powersOf10 = new int[10];
powersOf10[0] = 1;
for (int i = 1; i < 10; i++)
{
powersOf10[i] = powersOf10[i - 1] * 10;
}
var leftPowIndex = totalNumOfDigits - 1;
var rightPowIndex = 0;
while (leftPowIndex >= rightPowIndex)
{
var leftDigit = (num / powersOf10[leftPowIndex]) % 10;
var rightDigit = (num / powersOf10[rightPowIndex]) % 10;
if ((rightDigit * (powersOf10[leftPowIndex] / 10)) >= maxValueDiv10)
{
return 0;
}
if (leftPowIndex != rightPowIndex)
{
reversedNumber += leftDigit * powersOf10[rightPowIndex];
reversedNumber += rightDigit * powersOf10[leftPowIndex];
}
else
{
reversedNumber += leftDigit * powersOf10[leftPowIndex];
}
leftPowIndex--;
rightPowIndex++;
}
return isNegative ? -reversedNumber : reversedNumber;
}
To begin, we set up isNegative, reversedNumber, and totalNumOfDigits to manage the original number’s sign, reversed version, and digit count. The leftPowIndex and rightPowIndex variables track corresponding powers of 10 for the leftmost and rightmost digits.
Starting from both ends, we iterate through digit pairs using temporary variables leftDigit and rightDigit. We swap their positions by leveraging their respective powers of 10 and adding them to reversedNumber.
After each iteration leftPowIndex shifts right and rightPowIndex shifts left, effectively moving towards the middle digit. This continues until the loop finishes or surpasses the middle (for odd-numbered digits). The final result is the reversed integer.
We’ve explored different ways to reverse fixed-length integers, now let’s see how to reverse large numbers.
Reversing Large Numbers
While fixed-length data types like int handle integer reversal for smaller values, their susceptibility to overflow and underflow necessitates alternative approaches for larger numbers. We leverage the BigInteger data type, which empowers us to handle significantly larger numbers effortlessly.
Let’s dive into the specifics of customizing the digit extraction and reconstruction approach to handle large number reversal:
public static BigInteger ReverseUsingDigitExtractionAndReconstruction(BigInteger num)
{
BigInteger reversedNumber = 0;
while (num != 0)
{
var remainder = num % 10;
reversedNumber = reversedNumber * 10 + remainder;
num /= 10;
}
return reversedNumber;
}
Here. we declare the ReverseUsingDigitExtractionAndReconstruction() method, which takes the BigInteger parameter num. The remaining logic remains the same as we had for int datatype, except that we have removed the checks for overflow and underflow conditions.
BigInteger is a powerful tool for working with large integers, but it does have some disadvantages to consider. Due to their complexity, BigInteger operations are generally slower than working with native integer data types like int or long. This can be noticeable for frequent operations on large numbers. It also requires more memory to store as compared to primitive types.
We’ve explored different techniques to reverse a number as an integer, but choosing the optimal approach depends on real-world performance. Benchmarking helps us quantify the efficiency of each number reversal technique, guiding the selection for our specific needs.
Benchmarking Number Reversal Techniques
Benchmarks measure the execution time and memory usage of different code sections, helping identify the most efficient approaches. But, before we dive into our benchmark results, let’s familiarize ourselves with what each column represents.
Alright, now we’re ready to explore the benchmark results. For our benchmark, we set the ReverseAsString() method as the baseline, which represents the standard way of doing things.
Let’s benchmark all the integer reversal approaches for int datatype numbers:
| Method | Mean | Ratio | RatioSD | Gen0 | Allocated | |------------------------------- |----------:|------:|--------:|-------:|----------:| | Recursion_Int | 20.18 ns | 0.12 | 0.02 | - | - | | DigitExtractAndReconstruct_Int | 20.38 ns | 0.12 | 0.02 | - | - | | MathPow_Int | 48.29 ns | 0.30 | 0.04 | 0.0153 | 64 B | | SwappingDigits_Int | 52.11 ns | 0.32 | 0.04 | 0.0153 | 64 B | | ReverseAsString_Int | 166.77 ns | 1.00 | 0.00 | 0.0553 | 232 B |
We can see that the best approach to reversing a int type number is ReverseUsingDigitExtractionAndReconstruction(). It is due to its simplicity, reliance on efficient integer arithmetic, and avoidance of complex string operations. Our other approaches involve intricate mathematical operations that introduce additional overhead hence impacting performance.
Now, it’s time to see how our reversal techniques perform with large numbers. Let’s run our benchmark on a large 200-digit number:
| Method | Mean | Ratio | RatioSD | Gen0 | Allocated | |------------------------------------------ |-----------:|------:|--------:|--------:|----------:| | ReverseAsString_200DigitNumber | 2.733 us | 1.00 | 0.00 | 0.6752 | 2.76 KB | | DigitExtractAndReconstruct_200DigitNumber | 45.359 us | 16.56 | 1.50 | 9.7046 | 39.85 KB | | Recursion_200DigitNumber | 54.964 us | 20.13 | 3.36 | 9.7046 | 39.85 KB | | MathPow_200DigitNumber | 74.215 us | 27.20 | 5.14 | 14.8926 | 61.21 KB | | SwappingDigits_200DigitNumber | 131.924 us | 48.45 | 6.14 | 14.8926 | 61.35 KB |
For large numbers, such as those with 200 digits, reversing them as string often outperforms reversing them as BigInteger.
Conclusion
In this article, we explored various approaches to reverse a number as an integer. After that, we provided different benchmark results for each approach using small and big numbers for testing. This provided quite an interesting conclusion about which approaches are the most performant.
