Я написал класс с именем integer, который может обрабатывать целые числа произвольных размеров битов, и я, кажется, выполнил все, кроме одной вещи, которая, несмотря на все, что я делаю, чтобы попытаться это исправить, отказывается работать правильно:
std::ostream & operator<<(std::ostream & stream, integer rhs){
std::string out = "";
if (rhs == 0)
out = "0";
else {
int div = 10;
if (stream.flags() & stream.oct)
div = 8;
if (stream.flags() & stream.hex)
div = 16;
while (rhs){
// not doing mod to avoid dividing twice
integer next = rhs / div;
out = "0123456789abcdef"[(int) (rhs - next * div)] + out;
rhs = next;
}
}
stream << out;
return stream;
}
приведенный выше код дает мне самые странные ответы (не шестнадцатеричные символы, смешанные с правильными символами), при условии, что это не дает сбоя. я не понимаю почему. мое сложение, умножение вычитания и операторы деления верны. Типографское оформление правильное. внутренние значения (std :: deque), показанные в шестнадцатеричном формате, верны: 43981 покажет ab cd, когда cout редактируется перед циклом while. однако в цикле while я получу сумасшедшие значения, такие как 509, когда div = 10, несмотря на то, что уравнение в [] эквивалентно функции мода. все же вне этого кода в моем main.cpp я получу правильные значения.
что еще можно проверить?
РЕДАКТИРОВАТЬ: я не понимаю: я изменил внутри цикла while на:
integer next = rhs / div;
integer a = next * div;
integer b = rhs - a;
out = "0123456789abcdef"[(int) (b)] + out;
rhs = next;
и работает нормально. тем не менее, когда я перемещаю next * div на b вместо a, программа вылетает
edit2: здесь запрошенные операторы:
integer operator+(integer rhs){
if (rhs == 0)
return *this;
if (*this == 0)
return rhs;
std::deque <uint_fast8_t> top = value, bottom = rhs.value;
if (value.size() < rhs.value.size())
top.swap(bottom);
top.push_front(0);
while (bottom.size() + 1 < top.size())
bottom.push_front(0);
bool carry = false, next_carry;
for(std::deque <uint_fast8_t>::reverse_iterator i = top.rbegin(), j = bottom.rbegin(); j != bottom.rend(); i++, j++){
next_carry = ((*i + *j + carry) > 255);
*i += *j + carry;
carry = next_carry;
}
if (carry)
*top.begin() = 1;
return integer(top);
}
integer operator-(integer rhs){
if (rhs == 0)
return *this;
if (*this == rhs)
return integer(0);
if (rhs > *this)
exit(2);// to be worked on
unsigned int old_b = rhs.bits();
rhs = rhs.twos_complement();
for(unsigned int i = old_b; i < bits(); i++)
rhs ^= integer(1) << i;
return (*this + rhs) & (~(integer(1) << bits())); // Flip bits to get max of 1 << x
}
// Peasant Multiplication
integer peasant(integer lhs, integer rhs){
integer SUM = 0;
while (lhs){
if (lhs & 1)
SUM += rhs;
lhs >>= 1;
rhs <<= 1;
}
return SUM;
}
integer karatsuba(integer lhs, integer rhs){
// b is base = 256
// m is chars
// bm is max value
integer m = std::max(lhs.value.size(), rhs.value.size()) >> 1;
integer bm = 1;
bm <<= (m << 3);
if ((lhs < bm) || (rhs < bm))
return peasant(lhs, rhs);
integer x0 = lhs % bm;
integer x1 = lhs / bm;
integer y0 = rhs % bm;
integer y1 = rhs / bm;
integer z0 = karatsuba(x0, y0);
integer z2 = karatsuba(x1, y1);
integer z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0;
return karatsuba(karatsuba(z2, bm) + z1, bm) + z0;
}
const integer operator*(integer rhs){
integer lhs = *this;
return karatsuba(lhs, rhs);
}
integer operator/(integer rhs){
if (rhs == 0){
std::cout << "Error: division or modulus by zero" << std::endl;
exit(1);
}
if (rhs == 1)
return *this;
if (*this == rhs)
return integer(1);
if ((*this == 0) | (*this < rhs))
return integer(0);
// Check for divisors that are powers of two
uint16_t s = 0;
integer copyd(rhs);
while ((copyd & 1) == 0){
copyd >>= 1;
s++;
}
if (copyd == 1)
return *this >> s;
////////////////////////////////////////////////
integer copyn(*this), quotient = 0;
while (copyn >= rhs){
copyd = rhs;
integer temp(1);
while ((copyn >> 1) > copyd){
copyd <<= 1;
temp <<= 1;
}
copyn -= copyd;
quotient += temp;
}
return quotient;
}
integer operator%(integer rhs){
*this = *this - (*this / rhs) * rhs;
return *this;
}
полный код здесь .
Большое спасибо !!!