Circular right shift

[aurimas13]

Dear everyone,

I need to do a circular right shift to get 4552 from 5524 or 22266 from 22662 or 82719 from 27198. How it is possible to obtain such shift? I am puzzled on how to approach this problem. Thank you¡

Sincerely,
A.

[Moschops]

On the assumption that these are single integers, you could turn them into a string, go through the string copying everything to the right (be sure not to overwrite a value before you've moved it along), a single edge case to copy the one from the end back over the one at the start, and then turn that string back into an int.

[JLBorges]

Brute force

#include <string>
#include <limits>

unsigned long long circular_right_shift( unsigned int n )
{
    // http://en.cppreference.com/w/cpp/string/basic_string/to_string
    std::string str = std::to_string(n) ;
    
    // http://en.cppreference.com/w/cpp/algorithm/rotate
    // rotate left by n-1 is equivalent to rotate right by one
    std::rotate( str.begin(), str.begin()+str.size()-1, str.end() ) ;
    
    // http://en.cppreference.com/w/cpp/string/basic_string/stoul
    return std::stoull(str) ;
}

http://coliru.stacked-crooked.com/a/836d25c00bc8872c

[keskiverto]

You can use the operators / and % with loop to find and extract the most significant digit.

[aurimas13]

Thank you very much for the help. Links are great! Thanks.

[D80DSL3A]

My 2 cents. Good for integers

int rightShift( int x )
{
    if( x < 10 ) return x;

    int ltDigits = x/10, rtDigit = x%10;
    int tenPow = 10;
    while( tenPow < ltDigits ) tenPow *= 10;

    return tenPow*rtDigit + ltDigits;
}

edit: tenPow initial value from 1 to 10.

[JLBorges]

Two points:
1. With int rightShift( int x ) we would have to take care of x being negative
2. The result of the circular shift of an int may be outside the range of int (undefined behaviour)
http://coliru.stacked-crooked.com/a/112b9172e0e19aaa

[D80DSL3A]

Good points. Those are flaws.
The other flaw, low initial value for tenPow (1) caused trouble when ltDigits = 1.
before: rightShift( 14 ) --> 5
after: rightShift( 14 ) --> 41

[D80DSL3A]

OK. I can at least fix the negative value problem.I don't see what I can do about the out of range issue, so I won't address it. Avoid 10 1 + std::numeric_limits<int>::digits10 digit numbers?

#include <iostream>
#include <limits>

int rightShift( int x )
{
    int sign = 1;
    if( x < 0 )
    {
        sign = -1;
        x *= -1;
    }
    if( x < 10 ) return x *= sign;

    int ltDigits = x/10, rtDigit = x%10;
    int tenPow = 10;
    while( tenPow < ltDigits ) tenPow *= 10;

    return sign*( tenPow*rtDigit + ltDigits );
}

int main()
{
    int vals[] = {5524, 22662, 27198, 0, 14, -7345, -63, -7, std::numeric_limits<int>::max(), std::numeric_limits<int>::max()-6 };

    for( int n : vals ) std::cout << n << " --> " << rightShift(n) << '\n';

    return 0;
}

[JLBorges]

A different algorithm to rotate right by one
(reverse the first n-1 digits, append the last digit, and reverse the result.)

#include <limits>

static_assert( std::numeric_limits<long long>::digits10 > std::numeric_limits<int>::digits10, 
               "can't handle full range of int" ) ;

// invariant: n has fewer digits than std::numeric_limits<unsigned long long>::digits10
unsigned long long reverse( unsigned long long n ) 
{
    unsigned long long rev = 0 ;
    for( ; n != 0 ; n /= 10 ) rev = rev*10 + n%10 ;
    return rev ;
}

// invariant: n has fewer digits than std::numeric_limits<unsigned long long>::digits10
unsigned long long do_shift( unsigned long long n ) { return reverse( reverse(n/10) * 10 + n%10 ) ; }

long long circular_right_shift( int n ) { return n < 0 ? -do_shift( -(long long)n ) : do_shift(n) ; }

http://coliru.stacked-crooked.com/a/e7276564f9d293fc