/* Doesn't work with negative numbers :( Input: line 1: Non-negative Number line 2: Number of bits to shift */ #include #include std::string shiftLeft( const std::string& number ) { std::string result; bool shiftCarry = false; bool addCarry = false; for( int i = 0; i < number.size(); ++i ) { int digit = number[number.size()-i-1]-'0'; bool newCarry = (digit & 0x80) ? 1 : 0; int newDigit = (digit << 1 | shiftCarry) + addCarry; addCarry = false; shiftCarry = newCarry; if( newDigit > 9 ) { newDigit -= 10; addCarry = true; } result += newDigit + '0'; } if( addCarry ) result += '1'; std::reverse( result.begin(), result.end() ); return result; } std::string shiftLeft( const std::string& number, int n ) { std::string result = number; while( n-- ) result = shiftLeft( result ); return result; } std::string shiftRight( const std::string& number ) { std::string result; bool carry = false; for( int i = 0; i < number.size(); ++i ) { int digit = number[i] - '0'; bool newCarry = digit & 0x01; int newDigit = (digit >> 1) | ( carry ? 0x80 : 0x00 ); carry = newCarry; if( newDigit & 0x80 ) newDigit -= 0x7B; result += newDigit + '0'; } if( int firstNonZero = result.find_first_not_of( '0' ); firstNonZero != std::string::npos ) result = result.substr( firstNonZero ); return result; } std::string shiftRight( const std::string& number, int n ) { std::string result = number; while( n-- ) result = shiftRight( result ); return result; } int main() { std::string fail = "558609885306625372771138467627811336698018789891"; int failShifts = 75; std::string input; std::cin >> input; int shifts; if( !(std::cin >> shifts) || shifts < 0 ) { std::cout << "Invalid number entered for shift.\n"; shifts = failShifts; } bool valid = !input.empty(); for( auto i : input ) { if( !std::isdigit( i ) ) { valid = false; break; } } if( !valid ) { std::cout << "Invalid string entered.\n"; input = fail; } std::cout << input << " >> " << shifts << " =\n" << shiftRight( input, shifts ) << "\n\n"; std::cout << input << " << " << shifts << " =\n" << shiftLeft( input, shifts ) << '\n'; return 0; }

BigInteger bit shifting