I've been developing a C++ library for multiple precision computations (integers/fixed point), assume positive numbers.
The class is something like:
class Integer {
public:
//constructor
//destructor
//set
//overload operators
private;
uint32_t *mem;
int n_bits_stored;
};
Specifically the //overload operatos
has binary operators like
Integer Integer::operator+(const Integer& rhs);
Integer Integer::operator-(const Integer& rhs);
Integer Integer::operator*(const Integer& rhs);
Integer Integer::operator/(const Integer& rhs);
Integer Integer::operator%(const Integer& rhs);
but also
Integer Integer::operator<<(const int& l);
Integer Integer::operator>>(const int& l);
Integer& Integer::operator<<=(const int& l);
Integer& Integer::operator>>=(const int& l);
with the obvious meaning.
The idea is to extend the basic C++ integer types, other than you can change the bitwidth at real time.
Anyway... I'd like to overload the operator =
, that would convert a string
object to a Integer
object, something like
Integer x = "0xFE3425452783DFEABC34532FCAA"
(you can assume hex numbers are passed as string, so I can omit the prefix 0x
)
Here it is the approach I thought I could use
Input : a string
str
storing the hex digitsOutput : an
Integer
objectx
- Create a map
Map m
object where the key belong to the set{'0','1',...,'E','F'}
and the values are in the set{0,1,...,E,F}
(the former are characters, the latter are integers). - For each element in the map store the equivalent integer
- Init
x = 0
(assume also is already properly sized, eventually if the size is not enough then I can just chop the equivalent string). For
i = 0 ... str_digits.len-1
(the scanning should be from most significant digit to less significant digit).4.1.
x = x << 4
; //Left shifiting4.2.
x |= m[str[i]]
; //Implicit casting performedreturn
x
- Create a map
I know I'm missing some details but, you can assume that casting from integer types are implemented, as constructors, overload of every type of operators are implemented as well excepted for the the specific one I want to implement. Here there are my questions:
- Is my algorithm correct?
- Assuming it is correct is specifically the digit storing part implemented using Map data structure efficient? What concerns me a bit is the computational cost of fetching a digit, because in case where the base is high this approach could possibly be not efficient, right? What would you recommend otherwise?