Binary Division using Templated Big Integers

Question

I am trying to implement a Division Binary Algorithm.

The code has some Logical Errors which I am still trying to figure out how to fix them.

myuint operator/(const myuint<T>& x)
    {
        myuint<T> temp;
        myuint<T> result;

        int count = 0;

        for(int i = bits.size() - 1 ; i >= 0; --i)
        {
            temp.bits.push_back(bits[i]);

            if(temp >= x)
            {
                count++;
                *this = *this - x;
                temp = 0;
            }    
        }

        result = count;

        return result;
   }

I am also overloading the >=, >, and == operators for the division.

The logical problem most probably is in the for loop . What should I do? Thanks

Full code can be accessible from here

== EDIT

What I am trying to achieve is this. *this is 10100 (20 in decimal) x is 100 (4 in decimal)

1. Get the first Bit (1).
2. Compare it to x
3. If the bit is greater than the value of x, count++, subtract x from *this. And then Start the loop again which a different *this size.
4. If the bit is small, then we move to the bit next to it so, now we have 2 bits (10) and we compare it to x.
5. Then I return the value of count which represents this number of divisions to reach 0.

Answer 1

So, I found a simple implementation of how to go around Binary Division.

The idea is that you subtract the LSH from the RHS until LHS is smaller RHS and keep a hold for the many times you subtracted RHS from LSH.

myuint operator/(const myuint<T>& x)
{

    myuint<T> LHS = *this;
    myuint<T> RHS = x;
    myuint<T> result;

    int count = 0;
    bool flag = true;
    
    if(LHS == RHS)
    {
        return 1;
    }
    else
    {
        do
        {
            if(LHS >= RHS)
            {
                LHS = LHS - RHS;
                count++;
            }
            else if(LHS < RHS)
            {
                flag = false;
            }   
        }while(flag);
            
    }

    result = count;

    return result;
}

This may not be the most efficient way. But it gets the job done.

Answer 2

Not a full answer, but here is the algorithm that you need to implement:

myuint div(const myuint& x, const myuint& y)
{
    if (y == 0)
        throw "division by zero";

    myuint res = 0;
    myuint one = 1;

    unsigned int xLength = x.bitLength();
    unsigned int yLength = y.bitLength();

    while (xLength > yLength)
    {
        res += one << (xLength - yLength - 1);
        x -= y << (xLength - yLength - 1);
        xLength = x.bitLength();
    }

    if (x >= y)
        return res+1;
    return res;
}