Displaying large integers resulting in garbage

i wrote a class called integer that can handle integers of arbitrary bit sizes, and i seem to have completed everything except one thing, which despite everything that i do to try to fix it, refuses to work correctly:

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;
}

the code above gives me the weirdest answers (non-hex chars intermingled with correct chars) , assuming it doesnt crash. i dont get why. my addition, subtraction multiplication, and division operators are correct. the typecasting is correct. the internal values (std::deque) shown in hexadecimal is correct: 43981 will show ab cd when couted before the while loop. within the while loop, however, i will get crazy values like 509, when div = 10, despite the equation in the [] being equivalent to the mod function. yet outside this code in my main.cpp i will get the correct values.

what else is there to check?

EDIT: i dont get it: i changed the inside of the while loop to:

        integer next = rhs / div;
        integer a =  next * div;
        integer b = rhs - a;
        out = "0123456789abcdef"[(int) (b)] + out;
        rhs = next;

and it works fine. yet, when i move next * div to b to replace the a there, the program crashes

edit2: here are the operators, as requested:

    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;
    }

the full code is here.

thanks so much!!!

---

It's most likely an error in one of your operator implementations. Check the value of next. And introduce temporaries for next * div and rhs - next * div so you can verify the intermediate results. Also check the result of the cast to int.

Other thoughts:

• Don't use the same code for powers of two, those can be handled with simple bit shifts and masks.
• It's also worth avoiding string concatenation, calculate an upper bound on the required number of characters based on the number of bits, and then trim unneeded ones at the end.