Неограниченная реализация неподписанных целых целых связанных списков. Вычитание не работает

Question

Итак, я реализовал целый Unlimited Unsigned целочисленный класс, используя связанный список для проекта Euler, над которым я работаю. Я проверил, что все логические операции бит корректны (хотя я могу опубликовать их, если вы хотите их увидеть). Я уже реализовал все операторы и операции. Однако вычитание (и все его использование, т. Е. Деление и модуль) не работает. Когда я запускаю следующий тест, это то, что я получаю:

LimitlessUnsigned limitless = 0x88888888u; 
    limitless = limitless << 4; 

    LimitlessUnsigned tester = 0x88888884u; 
    tester = tester << 4; 

    //limitless = limitless >> 5; 
    LimitlessUnsigned another = limitless - tester; 

я получаю следующие значения из отладчика:

another LimitlessUnsigned 
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >  
[0] unsigned int 0b11111111111111111111111111111111 
[1] unsigned int 0b00000000000000000000000001000000 
limitless LimitlessUnsigned 
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >  
[0] unsigned int 0b00000000000000000000000000001000 
[1] unsigned int 0b10001000100010001000100010000000 
tester LimitlessUnsigned 
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >  
[0] unsigned int 0b00000000000000000000000000001000 
[1] unsigned int 0b10001000100010001000100001000000 

кажется, что я что-то пропустил с определением вычитания и два-х комплимент. Код работает, пока мне не нужно добавить дополнительные 32 бита. Я учитываю переполнение, начиная с первых 32 до следующего 32. Однако я отказываюсь от переполнения на самом высоком бите (как я и думал). Очевидно, что я делаю это неправильно. Ниже приведен соответствующий исходный код.

void LimitlessUnsigned::Sub(const LimitlessUnsigned& other) 
{ 
    if(*this <= other) 
    { 
    *this = 0u; 
    return; 
    } 

    LimitlessUnsigned temp = other; 

    while(temp.integerList.size() > integerList.size()) 
    integerList.push_front(0u); 

    while(integerList.size() > temp.integerList.size()) 
    temp.integerList.push_front(0u); 

    temp.TwosComp(); 
    Add(temp, true); 
} 
void LimitlessUnsigned::Add(const LimitlessUnsigned& other, bool allowRegisterLoss) 
{ 
    LimitlessUnsigned carry = *this & other; 
    LimitlessUnsigned result = *this^other; 

    while(carry != 0u) 
    { 
    carry.ShiftLeft(1, allowRegisterLoss); 
    LimitlessUnsigned shiftedcarry = carry; 
    carry = result & shiftedcarry; 
    result = result^shiftedcarry; 
    } 

*this = result; 
} 


void LimitlessUnsigned::Not() 
{ 
    for(std::list<unsigned>::iterator iter = integerList.begin(); iter != integerList.end(); ++iter) 
    {  
     *iter = ~*iter;  
    } 
} 

void LimitlessUnsigned::TwosComp() 
{ 
    Not(); 
    Add(1u, true); 
} 

void LimitlessUnsigned::ShiftLeft(unsigned shifts, bool allowRegisterLoss) 
{ 
    unsigned carry = 0u; 
    bool front_carry = false; 

    while(shifts > 0u) 
    {  
    if((integerList.front() & CARRY_INT_HIGH) == CARRY_INT_HIGH) 
     front_carry = true;  

    for(std::list<unsigned>::reverse_iterator iter = integerList.rbegin(); iter != integerList.rend(); ++iter) 
    {  
    unsigned temp = *iter; 

     *iter = *iter << 1; 
     *iter = *iter | carry;  

     if((temp & CARRY_INT_HIGH) == CARRY_INT_HIGH) 
     carry = CARRY_INT; 
     else 
     carry = 0u; 
    } 

    carry = 0u; 

    if(front_carry && !allowRegisterLoss) 
    { 
     front_carry = false; 
     integerList.push_front(1u); 
    } 

    --shifts;  
    } 
} 

Update я, наконец, решить эту проблему. Вот мой блог вместе с исходным кодом:

http://memmove.blogspot.com/2013/04/unlimited-unsigned-integer-in-c.html

Answer 1

После приема дополнительного кода вы добавляете, которая использует нулевое расширение, когда ширина не равны. Когда вы увеличиваете вычитание (теперь добавление) до ширины minuend, вам нужно использовать расширение знака, а не нулевое расширение. Это связано с тем, что в этом контексте ценность двоичного дополнения должна рассматриваться как отрицательное число (несмотря на то, что все не указано в другом месте). Альтернативно (и, возможно, больше в соответствии с общим дизайном), вычитание и minuend должны иметь одинаковую ширину, прежде чем начинать работу с двумя партнерами.

Вы делаете что-то вроде этого:

0110 - 10 = 0110 + (~(10) + 1) 
      = 0110 + (01 + 1) 
      = 0110 + 10 
      = 0110 + 0010 
      = 1000 

, когда он должен быть:

0110 - 10 = 0110 + (~(10) + 1) 
      = 0110 + (01 + 1) 
      = 0110 + 10 
      = 0110 + 1110 <= sign-extended subtrahend 
      = 0100 

или в качестве альтернативы:

0110 - 10 = 0110 - 0010 <= widths equalized 
      = 0110 + (~(0010) + 1) 
      = 0110 + (1101 + 1) 
      = 0110 + 1110 
      = 0100 

Answer 2

Давным время некоторые инженеры Data Control Корпорация (CDC) изобрела одноцилиндровый сумматор (до этого сумматор принимал один цикл на бит, распространяя carr y) и CDC запатентовали изобретение. Затем инженеры были наняты Крей, и им нужен быстрый сумматор. Поэтому умные инженеры придумали быстрый взгляд позади вычитателя заимствований, и Cray запатентовал это.

Моральный дух истории - это сложение и вычитание - это одно и то же, и ваш код вычитания должен выглядеть почти так же, как ваш код добавления.